제출 #1088742

#제출 시각아이디문제언어결과실행 시간메모리
1088742urd05Split the Attractions (IOI19_split)C++17
64 / 100
165 ms182756 KiB
#include "split.h" #include <bits/stdc++.h> using namespace std; typedef pair<int,int> P; vector<P> edge; vector<int> tree[1000005]; int ind[3]; int p[1000005]; int sz[1000005]; vector<int> ret; int find(int a) { return p[a]<0?a:p[a]=find(p[a]); } void merge(int a,int b) { a=find(a); b=find(b); if (a!=b) { p[a]+=p[b]; p[b]=a; } } void get_sz(int v,int pr) { sz[v]=1; for(int nt:tree[v]) { if (nt!=pr) { get_sz(nt,v); sz[v]+=sz[nt]; } } } int get_cent(int v,int pr,int half) { for(int nt:tree[v]) { if (nt==pr) { continue; } if (sz[nt]>half) { return get_cent(nt,v,half); } } return v; } bool vis[1000005]; bool vis1[1000005]; void bfs0(int v,int pr,int k,int x) { memset(vis,0,sizeof(vis)); queue<int> q; q.push(v); vis[v]=true; for(int i=0;i<k;i++) { int now=q.front(); q.pop(); ret[now]=x; for(int nt:tree[now]) { if (nt!=pr&&!vis[nt]) { q.push(nt); vis[nt]=true; } } } } int type[1000005]; void dfs_type(int v,int pr,int x) { type[v]=x; for(int nt:tree[v]) { if (nt!=pr) { dfs_type(nt,v,x); } } } vector<int> adj[1000005]; vector<int> adj1[1000005]; void bfs1(int v,int k,int x) { queue<int> q; q.push(v); memset(vis1,0,sizeof(vis1)); vis1[v]=true; for(int i=0;i<k;i++) { int now=q.front(); q.pop(); ret[now]=x; for(int nt:adj[now]) { if (vis[type[nt]]&&!vis1[nt]) { q.push(nt); vis1[nt]=true; } } } } void bfs2(int v,int k,int x) { queue<int> q; q.push(v); memset(vis1,0,sizeof(vis1)); vis1[v]=true; for(int i=0;i<k;i++) { int now=q.front(); q.pop(); ret[now]=x; for(int nt:adj[now]) { if (!vis[type[nt]]&&!vis1[nt]) { q.push(nt); vis1[nt]=true; } } } } vector<int> vec; queue<int> q; vector<int> find_split(int n, int a, int b, int c, vector<int> pp, vector<int> qq) { for(int i=0;i<3;i++) { ind[i]=i+1; } if (b>c) { swap(b,c); swap(ind[1],ind[2]); } if (a>b) { swap(a,b); swap(ind[0],ind[1]); } if (b>c) { swap(b,c); swap(ind[1],ind[2]); } ret.resize(n); for(int i=0;i<n;i++) { ret[i]=ind[2]; } for(int i=0;i<pp.size();i++) { adj[pp[i]].push_back(qq[i]); adj[qq[i]].push_back(pp[i]); edge.push_back(P(pp[i],qq[i])); } memset(p,-1,sizeof(p)); for(P x:edge) { if (find(x.first)!=find(x.second)) { merge(x.first,x.second); tree[x.first].push_back(x.second); tree[x.second].push_back(x.first); } } get_sz(0,-1); int ct=get_cent(0,-1,n/2); get_sz(ct,-1); type[ct]=ct; for(int nt:tree[ct]) { if (sz[nt]>=a) { bfs0(nt,ct,a,ind[0]); bfs0(ct,nt,b,ind[1]); return ret; } dfs_type(nt,ct,nt); } memset(vis,0,sizeof(vis)); for(P x:edge) { if (x.first==ct||x.second==ct) { continue; } if (type[x.first]!=type[x.second]) { adj1[type[x.first]].push_back(type[x.second]); adj1[type[x.second]].push_back(type[x.first]); } } memset(vis,0,sizeof(vis)); for(int nxt:tree[ct]) { if (vis1[nxt]) { continue; } q.push(nxt); vis[nxt]=true; int x=0; while (!q.empty()) { int now=q.front(); vec.push_back(now); q.pop(); x+=sz[now]; if (x>=a) { if (x<=n/2) { bfs1(now,a,ind[0]); bfs2(ct,b,ind[1]); } else { bfs1(now,b,ind[1]); bfs2(ct,a,ind[0]); } return ret; } for(int nt:adj1[now]) { if (!vis[nt]) { vis[nt]=true; q.push(nt); } } } for(int x:vec) { vis[x]=false; vis1[x]=true; } vec.clear(); } for(int i=0;i<n;i++) { ret[i]=0; } return ret; }

컴파일 시 표준 에러 (stderr) 메시지

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:142:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for(int i=0;i<pp.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...