제출 #837731

#제출 시각아이디문제언어결과실행 시간메모리
837731Desh03Split the Attractions (IOI19_split)C++17
0 / 100
1 ms212 KiB
#include "split.h" #include <bits/stdc++.h> using namespace std; struct DSU { vector<int> f; DSU(int n) { f.resize(n, -1); } int find(int u) { return f[u] < 0 ? u : f[u] = find(f[u]); } bool unite(int u, int v) { u = find(u), v = find(v); if (u == v) return 0; if (f[u] > f[v]) swap(u, v); f[u] += f[v]; f[v] = u; return 1; } }; vector<vector<int>> g; vector<int> sz, par, col; vector<pair<int, int>> f(3); int w, cnt; void dfs(int u) { sz[u] = 1; for (int v : g[u]) { if (v != par[u]) { par[v] = u; dfs(v); sz[u] += sz[v]; } } if (sz[u] >= f[0].first && g.size() - sz[u] >= f[1].first){ w = u; } } void dfs2(int u) { if (cnt < f[0].first) { cnt++; col[u] = f[0].second; } else { col[u] = f[2].second; } for (int v : g[u]) { if (v != par[u]) { dfs2(v); } } } void dfs3(int u) { if (cnt < f[1].first) { cnt++; col[u] = f[1].second; } else { col[u] = f[2].second; } for (int v : g[u]) { if (v != w && v != par[u]) { dfs3(v); } } } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { f = {{a, 1}, {b, 2}, {c, 3}}; sort(f.begin(), f.end()); g = vector<vector<int>> (n), sz = par = col = vector<int> (n); DSU ds(n); for (int i = 0; i < p.size(); i++) { if (ds.unite(p[i], q[i])) { g[p[i]].push_back(q[i]); g[q[i]].push_back(p[i]); } } for (int r : {rand() % n, rand() % n, rand() % n}) { do { w = -1, cnt = 0; dfs(r); if (w == -1) continue; dfs2(w); cnt = 0; dfs3(r); return col; } while (next_permutation(f.begin(), f.end())); } return col; }

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

split.cpp: In function 'void dfs(int)':
split.cpp:39:49: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |     if (sz[u] >= f[0].first && g.size() - sz[u] >= f[1].first){
      |                                ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int i = 0; i < p.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...