제출 #792183

#제출 시각아이디문제언어결과실행 시간메모리
792183APROHACKSplit the Attractions (IOI19_split)C++17
0 / 100
65 ms18108 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; int dp(int u){ vis[u] = true; int minimo = INT_MAX; if(A - (abajo[u] + 1) <= 0 and (abajo[u] + 1 < mejor)){ mejor = abajo[u] + 1; donde = u; minimo = abajo[u] + 1; //cout << "new best " << u << endl; } for(int i = 0 ; i < adj[u].size() ; i ++){ if(vis[adj[u][i]])continue; minimo = min ( minimo, dp(adj[u][i])); } if(A - (abajo[u] + 1) > 0)return minimo; else return min ( minimo, (abajo[u] + 1) ); } 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 --; 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 ; } } 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]); } memset(vis, false, sizeof vis); dfs(0); //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]; c = opt[2]; A = a; B = b; mejor = INT_MAX; for(int i = 0 ; i < n ; i++)respuesta.pb(0); memset(vis, false, sizeof vis); if(dp(0) == INT_MAX){ return respuesta; } int restantes = A - 1; memset(vis, false, sizeof vis); vis[donde] = true; int parent = 0; for(auto i : adj[donde]){ if(abajo[i] > abajo[donde]){ parent = i; continue; } generarSubArbol(i, 1, restantes); if(restantes <= 0 )break; } respuesta[donde] = 1; restantes = B; //cout << "donde " << donde << " parent " << parent << endl; generarSubArbol(parent, 2, restantes); for(int i = 0 ; i < n ; i ++)if(respuesta[i] == 0)respuesta[i] = 3; return respuesta; }

컴파일 시 표준 에러 (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 'int dp(int)':
split.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i = 0 ; i < adj[u].size() ; i ++){
      |                  ~~^~~~~~~~~~~~~~~
split.cpp: In function 'void generarSubArbol(int, int, int&)':
split.cpp:55:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for(int i = 0 ; i < adj[u].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...