library
This documentation is automatically generated by online-judge-tools/verification-helper
test/aoj/1599.test.cpp
- View this file on GitHub
- Last update: 2021-05-01 12:56:38+09:00
- Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1599
Depends on
Code
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1599
#include <bits/stdc++.h>
using namespace std;
#define call_from_test
#include "../../vector/compress.cpp"
#include "../../maxflow/dinic.cpp"
#undef call_from_test
int main(){
cin.tie(0);
ios::sync_with_stdio(0);
int n;
cin>>n;
vector<string> es(n);
for(int i=0;i<n;i++) cin>>es[i];
const int L=5;
vector<string> vs;
for(string &s:es){
for(char &c:s){
if(isdigit(c)) c=c-'0';
else c=c-'a'+10;
}
for(int i=0;i<L;i++){
if(s[i]&1) continue;
s[i]=(s[i]+1)%16;
vs.emplace_back(s);
s[i]=(s[i]+15)%16;
s[i]=(s[i]+15)%16;
vs.emplace_back(s);
s[i]=(s[i]+1)%16;
}
}
es=compress(es);
vs=compress(vs);
auto vd=dict(vs);
auto restore=
[](string s){
for(char &c:s){
if(c>=10) c='a'+(c-10);
else c='0'+c;
}
return s;
};
int m=vd.size();
Dinic<int, true> G(m+2);
int S=m,T=m+1;
vector<int> used(m,0);
using P = pair<int, int>;
map<string, P> mp;
for(string &s:es){
for(int i=0;i<L;i++){
if(s[i]&1) continue;
s[i]=(s[i]+1)%16;
int x=vd[s];
s[i]=(s[i]+15)%16;
s[i]=(s[i]+15)%16;
int y=vd[s];
s[i]=(s[i]+1)%16;
int sum=0;
for(char c:vs[x]) sum+=c/2;
if(sum&1) swap(x,y);
mp[s]=P(x,G.add_edge(x,y,1));
if(!used[x]){
mp[vs[x]]=P(S,G.add_edge(S,x,1));
used[x]=1;
}
if(!used[y]){
mp[vs[y]]=P(y,G.add_edge(y,T,1));
used[y]=1;
}
}
}
vector<string> as;
for(auto s:es) as.emplace_back(s);
for(auto s:vs) as.emplace_back(s);
sort(as.begin(),as.end());
cout<<G.flow(S,T)<<"\n";
for(auto s:as){
int x=mp[s].first;
int a=mp[s].second;
if(G.cut(S,T,x,a)==1){
cout<<restore(s)<<"\n";
}else{
G.link(S,T,x,a,1);
}
}
cout<<flush;
return 0;
}#line 1 "test/aoj/1599.test.cpp"
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1599
#include <bits/stdc++.h>
using namespace std;
#define call_from_test
#line 1 "vector/compress.cpp"
#line 3 "vector/compress.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename V>
V compress(V vs){
sort(vs.begin(),vs.end());
vs.erase(unique(vs.begin(),vs.end()),vs.end());
return vs;
}
template<typename T>
map<T, int> dict(const vector<T> &vs){
map<T, int> res;
for(int i=0;i<(int)vs.size();i++)
res[vs[i]]=i;
return res;
}
map<char, int> dict(const string &s){
return dict(vector<char>(s.begin(),s.end()));
}
template<typename T>
vector<T> compressed(vector<T> vs){
auto dc=dict(compress(vs));
for(auto &v:vs) v=dc[v];
return vs;
}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
return 0;
}
#endif
#line 1 "maxflow/dinic.cpp"
#line 3 "maxflow/dinic.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
// O(E V^2)
// O(E \min(E^{1/2}, V^{2/3})) if caps are constant
template<typename Flow,bool directed>
struct Dinic{
struct Edge {
int dst;
Flow cap;
int rev;
Edge(int dst,Flow cap,int rev):dst(dst),cap(cap),rev(rev){}
};
vector< vector<Edge> > G;
vector<int> level,iter;
Dinic(int n):G(n),level(n),iter(n){}
int add_edge(int src,int dst,Flow cap){
int e=G[src].size();
int r=(src==dst?e+1:G[dst].size());
G[src].emplace_back(dst,cap,r);
G[dst].emplace_back(src,directed?0:cap,e);
return e;
}
void bfs(int s){
fill(level.begin(),level.end(),-1);
queue<int> que;
level[s]=0;
que.emplace(s);
while(!que.empty()){
int v=que.front();que.pop();
for(Edge &e : G[v]) {
if(e.cap>0 and level[e.dst]<0){
level[e.dst]=level[v]+1;
que.emplace(e.dst);
}
}
}
}
Flow dfs(int v,int t,Flow f){
if(v==t) return f;
for(int &i=iter[v];i<(int)G[v].size();i++){
Edge &e=G[v][i];
if(e.cap>0 and level[v]<level[e.dst]){
Flow d=dfs(e.dst,t,min(f,e.cap));
if(d==0) continue;
e.cap-=d;
G[e.dst][e.rev].cap+=d;
return d;
}
}
return 0;
}
Flow flow(int s,int t,Flow lim){
Flow fl=0;
while(1){
bfs(s);
if(level[t]<0 or lim==0) break;
fill(iter.begin(),iter.end(),0);
while(1){
Flow f=dfs(s,t,lim);
if(f==0) break;
fl+=f;
lim-=f;
}
}
return fl;
}
Flow flow(int s,int t){
return flow(s,t,numeric_limits<Flow>::max()/2);
}
Flow cut(int s,int t,int x,int a){
static_assert(directed, "must be directed");
auto &e=G[x][a];
int y=e.dst;
Flow cr=G[y][e.rev].cap;
if(cr==0) return e.cap=0;
e.cap=G[y][e.rev].cap=0;
Flow cap=cr-flow(x,y,cr);
if(x!=s and cap!=0) flow(x,s,cap);
if(t!=y and cap!=0) flow(t,y,cap);
return cap;
}
Flow link(int s,int t,int x,int a,Flow f){
auto &e=G[x][a];
e.cap+=f;
return flow(s,t,f);
}
};
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
return 0;
}
#endif
#line 9 "test/aoj/1599.test.cpp"
#undef call_from_test
int main(){
cin.tie(0);
ios::sync_with_stdio(0);
int n;
cin>>n;
vector<string> es(n);
for(int i=0;i<n;i++) cin>>es[i];
const int L=5;
vector<string> vs;
for(string &s:es){
for(char &c:s){
if(isdigit(c)) c=c-'0';
else c=c-'a'+10;
}
for(int i=0;i<L;i++){
if(s[i]&1) continue;
s[i]=(s[i]+1)%16;
vs.emplace_back(s);
s[i]=(s[i]+15)%16;
s[i]=(s[i]+15)%16;
vs.emplace_back(s);
s[i]=(s[i]+1)%16;
}
}
es=compress(es);
vs=compress(vs);
auto vd=dict(vs);
auto restore=
[](string s){
for(char &c:s){
if(c>=10) c='a'+(c-10);
else c='0'+c;
}
return s;
};
int m=vd.size();
Dinic<int, true> G(m+2);
int S=m,T=m+1;
vector<int> used(m,0);
using P = pair<int, int>;
map<string, P> mp;
for(string &s:es){
for(int i=0;i<L;i++){
if(s[i]&1) continue;
s[i]=(s[i]+1)%16;
int x=vd[s];
s[i]=(s[i]+15)%16;
s[i]=(s[i]+15)%16;
int y=vd[s];
s[i]=(s[i]+1)%16;
int sum=0;
for(char c:vs[x]) sum+=c/2;
if(sum&1) swap(x,y);
mp[s]=P(x,G.add_edge(x,y,1));
if(!used[x]){
mp[vs[x]]=P(S,G.add_edge(S,x,1));
used[x]=1;
}
if(!used[y]){
mp[vs[y]]=P(y,G.add_edge(y,T,1));
used[y]=1;
}
}
}
vector<string> as;
for(auto s:es) as.emplace_back(s);
for(auto s:vs) as.emplace_back(s);
sort(as.begin(),as.end());
cout<<G.flow(S,T)<<"\n";
for(auto s:as){
int x=mp[s].first;
int a=mp[s].second;
if(G.cut(S,T,x,a)==1){
cout<<restore(s)<<"\n";
}else{
G.link(S,T,x,a,1);
}
}
cout<<flush;
return 0;
}