제출 #837685

#제출 시각아이디문제언어결과실행 시간메모리
837685Desh03Split the Attractions (IOI19_split)C++17
18 / 100
2074 ms15944 KiB
#include "split.h" #include <bits/stdc++.h> using namespace std; struct DSU { vector<int> f, sz; DSU(const int &n) { f.resize(n), sz.resize(n, 1); iota(f.begin(), f.end(), 0); } int find(const int &u) { return u == f[u] ? u : f[u] = find(f[u]); } bool unite(int u, int v) { u = find(u), v = find(v); if (u == v) return 0; if (sz[u] < sz[v]) swap(u, v); sz[u] += sz[v], f[v] = u; return 1; } }; vector<vector<int>> g; vector<int> sz, par, col; vector<pair<int, int>> f(3); int x, w, cnt, cnt2; 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 && sz[u] < x) { x = sz[u]; 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); } } } bool find_split(int root) { w = root, cnt = 0, x = g.size() + 1; par[root] = root; dfs(root); if (w == root) return 0; dfs2(w); cnt = 0; dfs3(root); if (cnt != f[1].first) return 0; return 1; } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { f[0] = {a, 1}, f[1] = {b, 2}, f[2] = {c, 3}, x = n + 1, cnt = cnt2 = w = 0; 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 i = 0; i < n; i++) { if (find_split(i)) return col; } return vector<int> (n); }

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

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