제출 #792268

#제출 시각아이디문제언어결과실행 시간메모리
792268APROHACKSplit the Attractions (IOI19_split)C++17
40 / 100
80 ms15912 KiB
#include "split.h" #include <bits/stdc++.h> #define ll long long #define ff first #define ss second #define pb push_back using namespace std; vector<int>adj[100005]; int N, m; bool vis[100005]; int abajo[100005], maximo[100005]; int dfs(int u){ vis[u] = true; abajo[u] = 0; maximo[u] = 0; int cu = 0; for(int i = 0 ; i < adj[u].size() ; i ++){ if(vis[adj[u][i]]){ continue; } cu = dfs(adj[u][i]); abajo[u] += cu; maximo[u] = max(maximo[u], cu); } return abajo[u] + 1; } vector<int> respuesta; int A, B; int mejor, donde; void dp(int u){ vis[u] = true; if(A - (abajo[u] + 1) <= 0 and (abajo[u] + 1 < mejor)){ mejor = abajo[u] + 1; donde = u; //cout << "new best " << u << endl; } for(int i = 0 ; i < adj[u].size() ; i ++){ if(vis[adj[u][i]])continue; dp(adj[u][i]); } } void generarSubArbol(int u, int val, int &restantes){ //cout << "generando " << u << " val " << val << " res " << restantes << endl; if(restantes <= 0){ return ; } vis [ u ] = true; respuesta[u] = val; restantes --; if(restantes <= 0)return ; for(int i = 0 ; i < adj[u].size() ; i ++){ if(vis[adj[u][i]])continue; generarSubArbol(adj[u][i], val, restantes); if(restantes <= 0)return ; } } int bfs(int st){ queue<int>cola; memset(vis, false, sizeof vis); cola.push(st); int distancia[N+3]; vis[st] = true; distancia[st] = 0; while(!cola.empty()){ int cur = cola.front(); cola.pop(); for(int i = 0 ; i < adj[cur].size() ; i ++){ if(vis[adj[cur][i]])continue; cola.push(adj[cur][i]); vis[adj[cur][i]] = true; distancia[adj[cur][i]] = distancia[cur] + 1; } } int hoja, dist = 0; for(int i = 0 ; i < N ; i ++){ if(distancia[i] > dist)hoja = i, dist = distancia[i]; } return hoja; } vector<int> test(int root, int a, int b, int c){ int n = N; vector<int>all0; for(int i = 0 ; i < n ; i ++)all0.pb(0); memset(vis, false, sizeof vis); dfs(root); //for(int i = 0 ; i < n ; i ++)cout << abajo[i] << endl; //cout << endl; vector<int> opt; opt.pb(a); opt.pb(b); opt.pb(c); sort(opt.begin(), opt.end()); A = opt[0]; B = opt[1]; mejor = INT_MAX; donde = root; respuesta.clear(); for(int i = 0 ; i < n ; i++)respuesta.pb(0); memset(vis, false, sizeof vis); dp(root); if(donde == root)return all0; int restantes = A - 1; memset(vis, false, sizeof vis); vis[donde] = true; int parent = root; for(auto i : adj[donde]){ if(abajo[i] >= abajo[donde]){ continue; } generarSubArbol(i, 1, restantes); if(restantes <= 0 )break; } respuesta[donde] = 1; restantes = B; //cout << "donde " << donde << " parent " << parent << endl; generarSubArbol(parent, 2, restantes); if(restantes > 0)return all0; for(int i = 0 ; i < n ; i ++)if(respuesta[i] == 0)respuesta[i] = 3; int mapeo[4]; bool banned[3]; memset(banned, false, sizeof banned); for(int i = 0 ; i < 3 ; i ++){ if(opt[i] == a and !banned[0]){ banned[0] = true; mapeo[i+1] = 1; }else if(opt[i] == b and !banned[1]){ banned[1] = true; mapeo[i+1] = 2; }else{ banned[2] = true; mapeo[i+1] = 3; } } for(int i = 0 ; i < n ; i++){ respuesta[i] = mapeo[respuesta[i]]; } return respuesta; } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { N = n; m = p.size(); for(int i = 0 ; i < m ; i ++){ adj[p[i]].pb(q[i]); adj[q[i]].pb(p[i]); } int rootA = bfs(0), rootB = bfs(rootA); vector<int>respA = test(rootA, a, b, c); if(respA[0] != 0){ return respA; }else return test(rootB, a, b, c); }

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

split.cpp: In function 'int dfs(int)':
split.cpp:17:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for(int i = 0 ; i < adj[u].size() ; i ++){
      |                  ~~^~~~~~~~~~~~~~~
split.cpp: In function 'void dp(int)':
split.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for(int i = 0 ; i < adj[u].size() ; i ++){
      |                  ~~^~~~~~~~~~~~~~~
split.cpp: In function 'void generarSubArbol(int, int, int&)':
split.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for(int i = 0 ; i < adj[u].size() ; i ++){
      |                  ~~^~~~~~~~~~~~~~~
split.cpp: In function 'int bfs(int)':
split.cpp:70:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   for(int i = 0 ; i < adj[cur].size() ; i ++){
      |                   ~~^~~~~~~~~~~~~~~~~
split.cpp:81:9: warning: 'hoja' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |  return hoja;
      |         ^~~~
#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...