cp-library
This documentation is automatically generated by online-judge-tools/verification-helper
verify/atcoder/abc347_g.cpp
- View this file on GitHub
- Last update: 2024-10-31 23:18:18+07:00
- Link: https://atcoder.jp/contests/abc347/tasks/abc347_g
Depends on
template.hpp
Code
#define PROBLEM "https://atcoder.jp/contests/abc347/tasks/abc347_g"
#include "template.hpp"
#include "flow/k-ary-optimization.hpp"
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
vector a(n,vector<int>(n));
for(auto &v:a)for(auto &x:v)cin >> x,x--;
K_aryOptimization<ll,true> s(n*n,5);
auto enc=[&](int i,int j){return i*n+j;};
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(a[i][j]!=-1){
vector<ll> c(5,INF);
c[a[i][j]]=0;
s.add1(enc(i,j),c);
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int u=enc(i,j);
auto work=[&](int x,int y){
if(x<0||x>=n||y<0||y>=n)return;
int v=enc(x,y);
vector c(5,vector<ll>(5));
for(int x1=0;x1<5;x1++){
for(int x2=0;x2<5;x2++){
c[x1][x2]=(x1-x2)*(x1-x2);
}
}
s.add2(u,v,c);
};
work(i,j+1);
work(i+1,j);
}
}
auto ans=s.solve().second;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout << ans[enc(i,j)]+1 << " \n"[j==n-1];
}
}
}#line 1 "verify/atcoder/abc347_g.cpp"
#define PROBLEM "https://atcoder.jp/contests/abc347/tasks/abc347_g"
#line 1 "template.hpp"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using db = long double;
using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<db>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pdd = pair<db,db>;
const int INF=INT_MAX/2;
const int MOD=998244353;
const int MOD2=1000000007;
const ll LINF=LLONG_MAX/2;
const db DINF=numeric_limits<db>::infinity();
const db EPS=1e-9;
const db PI=acos(db(-1));
template<class T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
template<class T>
using ordered_multiset = tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
#line 2 "flow/dinic.hpp"
/**
* Author: Teetat T.
* Date: 2024-07-15
* Description: Dinic's Algorithm for finding the maximum flow.
* Time: O(V E \log U) where U is the maximum flow.
*/
template<class T,bool directed=true,bool scaling=true>
struct Dinic{
static constexpr T INF=numeric_limits<T>::max()/2;
struct Edge{
int to;
T flow,cap;
Edge(int _to,T _cap):to(_to),flow(0),cap(_cap){}
T remain(){return cap-flow;}
};
int n,s,t;
T U;
vector<Edge> e;
vector<vector<int>> g;
vector<int> ptr,lv;
bool calculated;
T max_flow;
Dinic(){}
Dinic(int n,int s,int t){init(n,s,t);}
void init(int _n,int _s,int _t){
n=_n,s=_s,t=_t;
U=0;
e.clear();
g.assign(n,{});
calculated=false;
}
void add_edge(int from,int to,T cap){
assert(0<=from&&from<n&&0<=to&&to<n);
g[from].emplace_back(e.size());
e.emplace_back(to,cap);
g[to].emplace_back(e.size());
e.emplace_back(from,directed?0:cap);
U=max(U,cap);
}
bool bfs(T scale){
lv.assign(n,-1);
vector<int> q{s};
lv[s]=0;
for(int i=0;i<(int)q.size();i++){
int u=q[i];
for(int j:g[u]){
int v=e[j].to;
if(lv[v]==-1&&e[j].remain()>=scale){
q.emplace_back(v);
lv[v]=lv[u]+1;
}
}
}
return lv[t]!=-1;
}
T dfs(int u,int t,T f){
if(u==t||f==0)return f;
for(int &i=ptr[u];i<(int)g[u].size();i++){
int j=g[u][i];
int v=e[j].to;
if(lv[v]==lv[u]+1){
T res=dfs(v,t,min(f,e[j].remain()));
if(res>0){
e[j].flow+=res;
e[j^1].flow-=res;
return res;
}
}
}
return 0;
}
T flow(){
if(calculated)return max_flow;
calculated=true;
max_flow=0;
for(T scale=scaling?1LL<<(63-__builtin_clzll(U)):1LL;scale>0;scale>>=1){
while(bfs(scale)){
ptr.assign(n,0);
while(true){
T f=dfs(s,t,INF);
if(f==0)break;
max_flow+=f;
}
}
}
return max_flow;
}
pair<T,vector<int>> cut(){
flow();
vector<int> res(n);
for(int i=0;i<n;i++)res[i]=(lv[i]==-1);
return {max_flow,res};
}
};
#line 3 "flow/k-ary-optimization.hpp"
/**
* Author: Teetat T.
* Date: 2024-07-16
* Description: k-ary Optimization.
* minimize $\kappa + \sum_i \theta_i(x_i) + \sum_{i<j} \phi_{ij}(x_i,x_j)$
* where $x_i \in \{0,1,\ldots,k-1\}$ and $\phi_{i,j}$ is monge.
* A function $f$ is monge if $f(a,c)+f(b,d) \leq f(a,d)+f(b,c)$ for all $a < b$ and $c < d$.
* $\phi_{ij}(x-1,y)+\phi_{ij}(x,y+1) \leq \phi_{ij}(x-1,y+1)+\phi_{ij}(x,y)$.
* $\phi_{ij}(x,y)+\phi_{ij}(x-1,y+1)-\phi_{ij}(x-1,y)-\phi_{ij}(x,y+1) \geq 0$.
*/
template<class T,bool minimize=true>
struct K_aryOptimization{
static constexpr T INF=numeric_limits<T>::max()/2;
int n,s,t,node_id;
T base;
vector<int> ks;
vector<vector<int>> id;
map<pair<int,int>,T> edges;
K_aryOptimization(int n,int k){init(vector<int>(n,k));}
K_aryOptimization(const vector<int> &_ks){init(_ks);}
void init(const vector<int> &_ks){
ks=_ks;
n=ks.size();
s=0,t=1,node_id=2;
base=0;
id.clear();
edges.clear();
for(auto &k:ks){
assert(k>=1);
vector<int> a(k+1);
a[0]=s,a[k]=t;
for(int i=1;i<k;i++)a[i]=node_id++;
id.emplace_back(a);
for(int i=2;i<k;i++)add_edge(a[i],a[i-1],INF);
}
}
void add_edge(int u,int v,T w){
assert(w>=0);
if(u==v||w==0)return;
auto &e=edges[{u,v}];
e=min(e+w,INF);
}
void add0(T w){
base+=w;
}
void _add1(int i,vector<T> cost){
add0(cost[0]);
for(int j=1;j<ks[i];j++){
T x=cost[j]-cost[j-1];
if(x>0)add_edge(id[i][j],t,x);
if(x<0)add0(x),add_edge(s,id[i][j],-x);
}
}
void add1(int i,vector<T> cost){
assert(0<=i&&i<n&&(int)cost.size()==ks[i]);
if(!minimize)for(auto &x:cost)x=-x;
_add1(i,cost);
}
void _add2(int i,int j,vector<vector<T>> cost){
int h=ks[i],w=ks[j];
_add1(j,cost[0]);
for(int x=h-1;x>=0;x--)for(int y=0;y<w;y++)cost[x][y]-=cost[0][y];
vector<T> a(h);
for(int x=0;x<h;x++)a[x]=cost[x][w-1];
_add1(i,a);
for(int x=0;x<h;x++)for(int y=0;y<w;y++)cost[x][y]-=a[x];
for(int x=1;x<h;x++){
for(int y=0;y<w-1;y++){
T w=cost[x][y]+cost[x-1][y+1]-cost[x-1][y]-cost[x][y+1];
assert(w>=0); // monge
add_edge(id[i][x],id[j][y+1],w);
}
}
}
void add2(int i,int j,vector<vector<T>> cost){
assert(0<=i&&i<n&&0<=j&&j<n&&i!=j);
assert((int)cost.size()==ks[i]);
for(auto &v:cost)assert((int)v.size()==ks[j]);
if(!minimize)for(auto &v:cost)for(auto &x:v)x=-x;
_add2(i,j,cost);
}
pair<T,vector<int>> solve(){
Dinic<T> dinic(node_id,s,t);
for(auto &[p,w]:edges){
auto [u,v]=p;
dinic.add_edge(u,v,w);
}
auto [val,cut]=dinic.cut();
val+=base;
if(!minimize)val=-val;
vector<int> ans(n);
for(int i=0;i<n;i++){
ans[i]=ks[i]-1;
for(int j=1;j<ks[i];j++)ans[i]-=cut[id[i][j]];
}
return {val,ans};
}
};
#line 4 "verify/atcoder/abc347_g.cpp"
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
vector a(n,vector<int>(n));
for(auto &v:a)for(auto &x:v)cin >> x,x--;
K_aryOptimization<ll,true> s(n*n,5);
auto enc=[&](int i,int j){return i*n+j;};
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(a[i][j]!=-1){
vector<ll> c(5,INF);
c[a[i][j]]=0;
s.add1(enc(i,j),c);
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int u=enc(i,j);
auto work=[&](int x,int y){
if(x<0||x>=n||y<0||y>=n)return;
int v=enc(x,y);
vector c(5,vector<ll>(5));
for(int x1=0;x1<5;x1++){
for(int x2=0;x2<5;x2++){
c[x1][x2]=(x1-x2)*(x1-x2);
}
}
s.add2(u,v,c);
};
work(i,j+1);
work(i+1,j);
}
}
auto ans=s.solve().second;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout << ans[enc(i,j)]+1 << " \n"[j==n-1];
}
}
}