Submission #198418

#TimeUsernameProblemLanguageResultExecution timeMemory
198418FerThugGato12500Split the Attractions (IOI19_split)C++14
0 / 100
10 ms5368 KiB
#include<iostream> #include<algorithm> #include<vector> #include<string.h> #include<split.h> using namespace std; vector<int> ed[100001]; int need[3]; int n, m; bool vis[100001]; int cld[100001]; int dfs(int ind) { int D=1; vis[ind]=true; for(int i = 0; i < ed[ind].size(); i++) if(!vis[ed[ind][i]]) D+=dfs(ed[ind][i]); return (cld[ind] = D); } int bus(int ind) { bool z=true; vis[ind]=true; for(int i = 0; i < ed[ind].size(); i++) if(!vis[ed[ind][i]] && cld[ed[ind][i]]>=n/2) z=false; if(n-cld[ind]>=n/2) z=false; if(z) return ind; int D=-1; for(int i = 0; i < ed[ind].size(); i++) if(!vis[ed[ind][i]]) D=max(bus(ed[ind][i]), D); return D; } int centroide() { dfs(1); memset(vis, false, sizeof(vis)); return bus(1); } vector<int> ans[3]; int rey; typedef struct { int to, cld; }Wasd; bool operator < (const Wasd &a, const Wasd &b) { return a.cld < b.cld; } void expand(int ind) { vis[ind]=true; ans[rey].push_back(ind); if(ans[rey].size()==need[rey]) return; for(int i = 0; i < ed[ind].size(); i++) if(!vis[ed[ind][i]] && ans[rey].size()<need[rey]) expand(ed[ind][i]); return; } int res[100001]; vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) { n=N; need[0]=a; need[1]=b; need[2]=c; m=p.size(); int x, y; for(int i = 0; i < m; i++) { x=p[i]; y=q[i]; ed[x].push_back(y); ed[y].push_back(x); } int cnt = centroide(); if(need[0]<=max(need[1], need[2]) && need[0]>=min(need[2], need[1])) rey=0; else if(need[1]<=max(need[0], need[2]) && need[1]>=min(need[2], need[0])) rey=1; else rey=2; memset(vis, false, sizeof(vis)); expand(cnt); if(need[0]<=need[1] && need[0]<=need[2]) rey=0; else if(need[1]<=need[0] && need[1]<=need[2]) rey=1; else rey=2; for(int i = 0; i < n; i++) if(!vis[i]) { expand(i); if(ans[rey].size()==need[rey]) break; ans[rey].clear(); } for(int k = 0; k < 3; k++) for(int i = 0; i < ans[k].size(); i++) res[ans[k][i]]=k+1; if(ans[0].size()>0 && ans[1].size()>0) rey=2; else if(ans[1].size()>0 && ans[2].size()>0) rey=0; else rey=1; for(int i = 0; i < n; i++) if(res[i]==0) res[i] = rey+1; vector<int> respuesta; for(int i = 0; i < n; i++) respuesta.push_back(res[i]); return respuesta; }

Compilation message (stderr)

split.cpp: In function 'int dfs(int)':
split.cpp:16:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ed[ind].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
split.cpp: In function 'int bus(int)':
split.cpp:25:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ed[ind].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
split.cpp:32:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ed[ind].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
split.cpp: In function 'void expand(int)':
split.cpp:57:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(ans[rey].size()==need[rey])
     ~~~~~~~~~~~~~~~^~~~~~~~~~~
split.cpp:59:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < ed[ind].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
split.cpp:60:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(!vis[ed[ind][i]] && ans[rey].size()<need[rey])
                          ~~~~~~~~~~~~~~~^~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:93:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(ans[rey].size()==need[rey])
       ~~~~~~~~~~~~~~~^~~~~~~~~~~
split.cpp:98:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < ans[k].size(); i++)
                  ~~^~~~~~~~~~~~~~~
#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...