Submission #161752

#TimeUsernameProblemLanguageResultExecution timeMemory
161752andrewSplit the Attractions (IOI19_split)C++17
7 / 100
138 ms37560 KiB
#include <bits/stdc++.h> #include "split.h" #define fi first #define se second #define pll pair<ll, ll> #define pii pair<int, int> using namespace std; typedef long long ll; typedef long double ld; const ll MAXN = 1123456; const ll N = 2e5; vector <int> v[MAXN]; int start; bool f[N]; vector <ll> d; void dfs(int x, int pr){ if(f[x] == 1){ start = x; return; } if(f[x] == 2)return; f[x] = 1; for(auto to : v[x])if(to != pr)dfs(to, x); f[x] = 2; } int C; void go(int x){ if(f[x])return; if(!C)return; C--; d.push_back(x); f[x] = 1; for(auto to : v[x])go(to); } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { int m = p.size(), mx = 0; C = c; for(int i = 0; i < m; i++){ v[p[i]].push_back(q[i]); v[q[i]].push_back(p[i]); mx = max(mx, (int)v[p[i]].size()); mx = max(mx, (int)v[q[i]].size()); } vector <int> res(n); if(a == 1){ queue <int> q; start = 0; // for(int i = 0; i < n; i++)if(v[i].size() == 1)start = i; // if(v[start].size() != 1){ // dfs(1, 0); // } q.push(start); f[start] = 1; res[start] = 1; for(auto to : v[start])go(to); for(auto i : d)res[i] = 3; for(int i = 0; i < n; i++)if(res[i] == 0)res[i] = 2; return res; }else if(mx < 3){ int F = 0, Last = 0; for(int i = 0; i < n; i++)if(v[i].size() == 1)F = i; int step = 1; vector <int> cnt(3); cnt[0] = a; cnt[1] = b; cnt[2] = c; for(int i = 0; i < n; i++){ if(i){ int New = 0; for(auto j : v[F])if(j != Last)New = j; Last = F; F = New; } while(!cnt[step - 1])step++; --cnt[step - 1]; res[F] = step; } return res; }else{ return res; } return res; }

Compilation message (stderr)

split.cpp: In function 'void dfs(int, int)':
split.cpp:29:13: warning: comparison of constant '2' with boolean expression is always false [-Wbool-compare]
     if(f[x] == 2)return;
        ~~~~~^~~~
#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...