Submission #785670

#TimeUsernameProblemLanguageResultExecution timeMemory
7856701binSplit the Attractions (IOI19_split)C++14
18 / 100
75 ms21888 KiB
#include <bits/stdc++.h> //#include "split.h" using namespace std; #define all(v) v.begin(), v.end() typedef long long ll; const int NMAX = 1e5 + 5; int ans, n, A, B, label[NMAX], cnt; int dfsn[NMAX], low[NMAX], sz[NMAX], t; vector<int> adj[NMAX]; void color(int x, int c){ if(label[x] != -1) return; label[x] = (cnt-- > 0 ? c : 2); for(int& nx : adj[x]) if(dfsn[nx] > dfsn[x]) color(nx, c); return; } void dfs(int x, int p){ vector<int> C; dfsn[x] = low[x] = ++t; sz[x] = 1; int mx = 0; for(int& nx : adj[x]) if(nx != p) { if(!dfsn[nx]){ dfs(nx, x); low[x] = min(low[x], low[nx]); sz[x] += sz[nx]; C.emplace_back(nx); mx = max(mx, sz[nx]); } else low[x] = min(low[x], dfsn[nx]); } if(!ans && sz[x] >= A && mx < A){ int d = sz[x], u = n - d; label[x] = 0; cnt = A - 1; for(int& nx : C){ if(d - sz[nx] >= A && low[nx] < dfsn[x]) u += sz[nx], d -= sz[nx]; else color(nx, 0); } ans = (u >= A ? 1 : -1); } return; } vector<int> find_split(int n_, int a, int b, int c, vector<int> p, vector<int> q) { n = n_; vector<pair<int, int>> arr = {{a, 1}, {b, 2}, {c, 3}}; sort(all(arr)); A = arr[0].first; B = arr[1].first; vector<int> res(n, 0); for(int i = 0; i < p.size(); i++){ adj[p[i]].emplace_back(q[i]); adj[q[i]].emplace_back(p[i]); } memset(label, -1, sizeof(label)); dfs(0, -1); if(ans == -1) return res; cnt = B; color(0, 1); for(int i = 0; i < n; i++) res[i] = arr[label[i]].second; return res; } /* int main(void){ int n, m, a, b, c; cin >> n >> a >> b >> c; cin >> m; vector<int> p(m), q(m); for(int i = 0; i < m; i++) cin >> p[i] >> q[i]; auto v = find_split(n, a, b, c, p, q); for(int& x : v) cout << x << ' '; return 0; } */

Compilation message (stderr)

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