Submission #726856

#TimeUsernameProblemLanguageResultExecution timeMemory
726856alvingogoSplit the Attractions (IOI19_split)C++14
100 / 100
177 ms27152 KiB
#include "split.h" #include <bits/stdc++.h> //#include "grader.cpp" #define fs first #define sc second using namespace std; vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { int m=p.size(); vector<vector<int> > e(n); for(int i=0;i<m;i++){ e[p[i]].push_back(q[i]); e[q[i]].push_back(p[i]); } vector<int> ans(n); pair<int,int> rk[3]={{a,1},{b,2},{c,3}}; if(a>b){ swap(rk[0],rk[1]); } if(b>c){ swap(rk[1],rk[2]); } vector<int> vis(n),vis2(n); int flag=0; vector<int> sz(n),dep(n); function<void(int)> dfs3=[&](int r){ ans[r]=rk[1].sc; vis2[r]=1; rk[1].fs--; if(rk[1].fs==0){ return; } for(auto h:e[r]){ if(!vis2[h]){ dfs3(h); if(rk[1].fs==0){ return; } } } }; function<void(int)> dfs2=[&](int r){ ans[r]=rk[0].sc; vis2[r]=1; rk[0].fs--; if(rk[0].fs==0){ return; } for(auto h:e[r]){ if(dep[h]==dep[r]+1){ dfs2(h); if(rk[0].fs==0){ return; } } } }; function<int(int,int)> dfs=[&](int r,int d){ dep[r]=d; vis[r]=1; sz[r]=1; int f3=0; int x=1e9; vector<pair<int,int> > zz; for(auto h:e[r]){ if(!vis[h]){ int u=dfs(h,d+1); x=min(x,u); if(u<dep[r]){ zz.push_back({sz[h],h}); } sz[r]+=sz[h]; if(sz[h]>=rk[0].fs){ f3=1; } if(flag){ return (int)1e9; } } else{ x=min(x,dep[h]); } } if(flag){ return (int)1e9; } if(!f3){ if(sz[r]>=rk[0].fs){ int u=n-sz[r]; int f2=0; for(int i=0;i<=zz.size();i++){ if(u>=rk[1].fs){ dfs2(r); for(auto h:e[r]){ if(dep[h]==dep[r]-1){ dfs3(h); break; } } break; } if(i==zz.size()){ f2=1; break; } u+=zz[i].fs; dep[zz[i].sc]=-2; } if(f2){ } else{ for(int j=0;j<n;j++){ if(ans[j]==0){ ans[j]=rk[2].sc; } } flag=1; return (int)1e9; } } } return x; }; dfs(0,0); if(flag){ return ans; } swap(rk[0],rk[1]); fill(vis.begin(),vis.end(),0); fill(sz.begin(),sz.end(),0); fill(dep.begin(),dep.end(),0); dfs(0,0); return ans;}

Compilation message (stderr)

split.cpp: In lambda function:
split.cpp:6:1327: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | using namespace std; vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { int m=p.size(); vector<vector<int> > e(n); for(int i=0;i<m;i++){  e[p[i]].push_back(q[i]);  e[q[i]].push_back(p[i]); } vector<int> ans(n); pair<int,int> rk[3]={{a,1},{b,2},{c,3}}; if(a>b){  swap(rk[0],rk[1]); } if(b>c){  swap(rk[1],rk[2]); } vector<int> vis(n),vis2(n); int flag=0; vector<int> sz(n),dep(n); function<void(int)> dfs3=[&](int r){  ans[r]=rk[1].sc;  vis2[r]=1;  rk[1].fs--;  if(rk[1].fs==0){   return;  }  for(auto h:e[r]){   if(!vis2[h]){    dfs3(h);    if(rk[1].fs==0){     return;    }   }  } }; function<void(int)> dfs2=[&](int r){  ans[r]=rk[0].sc;  vis2[r]=1;  rk[0].fs--;  if(rk[0].fs==0){   return;  }  for(auto h:e[r]){   if(dep[h]==dep[r]+1){    dfs2(h);    if(rk[0].fs==0){     return;    }   }  } }; function<int(int,int)> dfs=[&](int r,int d){  dep[r]=d;  vis[r]=1;  sz[r]=1;  int f3=0;  int x=1e9;  vector<pair<int,int> > zz;  for(auto h:e[r]){   if(!vis[h]){    int u=dfs(h,d+1);    x=min(x,u);    if(u<dep[r]){     zz.push_back({sz[h],h});    }    sz[r]+=sz[h];    if(sz[h]>=rk[0].fs){     f3=1;    }    if(flag){     return (int)1e9;    }   }   else{    x=min(x,dep[h]);   }  }  if(flag){   return (int)1e9;  }  if(!f3){   if(sz[r]>=rk[0].fs){    int u=n-sz[r];    int f2=0;    for(int i=0;i<=zz.size();i++){     if(u>=rk[1].fs){      dfs2(r);      for(auto h:e[r]){       if(dep[h]==dep[r]-1){        dfs3(h);        break;       }      }      break;     }     if(i==zz.size()){      f2=1;      break;     }     u+=zz[i].fs;     dep[zz[i].sc]=-2;    }    if(f2){         }    else{     for(int j=0;j<n;j++){      if(ans[j]==0){       ans[j]=rk[2].sc;      }     }     flag=1;     return (int)1e9;    }   }  }  return x; }; dfs(0,0); if(flag){  return ans; } swap(rk[0],rk[1]); fill(vis.begin(),vis.end(),0); fill(sz.begin(),sz.end(),0); fill(dep.begin(),dep.end(),0); dfs(0,0); return ans;}
      |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              ~^~~~~~~~~~~
split.cpp:6:1502: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | using namespace std; vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { int m=p.size(); vector<vector<int> > e(n); for(int i=0;i<m;i++){  e[p[i]].push_back(q[i]);  e[q[i]].push_back(p[i]); } vector<int> ans(n); pair<int,int> rk[3]={{a,1},{b,2},{c,3}}; if(a>b){  swap(rk[0],rk[1]); } if(b>c){  swap(rk[1],rk[2]); } vector<int> vis(n),vis2(n); int flag=0; vector<int> sz(n),dep(n); function<void(int)> dfs3=[&](int r){  ans[r]=rk[1].sc;  vis2[r]=1;  rk[1].fs--;  if(rk[1].fs==0){   return;  }  for(auto h:e[r]){   if(!vis2[h]){    dfs3(h);    if(rk[1].fs==0){     return;    }   }  } }; function<void(int)> dfs2=[&](int r){  ans[r]=rk[0].sc;  vis2[r]=1;  rk[0].fs--;  if(rk[0].fs==0){   return;  }  for(auto h:e[r]){   if(dep[h]==dep[r]+1){    dfs2(h);    if(rk[0].fs==0){     return;    }   }  } }; function<int(int,int)> dfs=[&](int r,int d){  dep[r]=d;  vis[r]=1;  sz[r]=1;  int f3=0;  int x=1e9;  vector<pair<int,int> > zz;  for(auto h:e[r]){   if(!vis[h]){    int u=dfs(h,d+1);    x=min(x,u);    if(u<dep[r]){     zz.push_back({sz[h],h});    }    sz[r]+=sz[h];    if(sz[h]>=rk[0].fs){     f3=1;    }    if(flag){     return (int)1e9;    }   }   else{    x=min(x,dep[h]);   }  }  if(flag){   return (int)1e9;  }  if(!f3){   if(sz[r]>=rk[0].fs){    int u=n-sz[r];    int f2=0;    for(int i=0;i<=zz.size();i++){     if(u>=rk[1].fs){      dfs2(r);      for(auto h:e[r]){       if(dep[h]==dep[r]-1){        dfs3(h);        break;       }      }      break;     }     if(i==zz.size()){      f2=1;      break;     }     u+=zz[i].fs;     dep[zz[i].sc]=-2;    }    if(f2){         }    else{     for(int j=0;j<n;j++){      if(ans[j]==0){       ans[j]=rk[2].sc;      }     }     flag=1;     return (int)1e9;    }   }  }  return x; }; dfs(0,0); if(flag){  return ans; } swap(rk[0],rk[1]); fill(vis.begin(),vis.end(),0); fill(sz.begin(),sz.end(),0); fill(dep.begin(),dep.end(),0); dfs(0,0); return ans;}
      |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...