Submission #1278070

#TimeUsernameProblemLanguageResultExecution timeMemory
1278070al95ireyizSplit the Attractions (IOI19_split)C++20
0 / 100
2094 ms11576 KiB
#pragma GCC optimize("O3", "fast-math", "unroll-loops", "no-stack-protector") #include <bits/stdc++.h> using namespace std; #if !defined(ONLINE_JUDGE) and !defined(EVAL) #include "template/debug.h" #else #define d(x...) #endif #define fr first #define er erase #define in insert #define sc second #define ll long long #define pb push_back #define vll vector<ll> #define pll pair<ll,ll> #define len(x) (ll) x.size() #define all(x) x.begin(),x.end() const ll INF = 1e9, INFL = 1e18; const ll MOD = 1e9 + 7; // const ll MOD = 998244353; const ll maxn = 1e5 + 5; ll n, m, k = 0; vll g[maxn]; ll a, b, c; bitset<maxn>vis; vector<int>cv; // not ez ll dfs(ll u){ ll le = 1; vis[u] = 1; for(auto v : g[u]){ if(vis[v]) continue; le += dfs(v); } return le; } ll cal[4]; void dfs1(ll u, ll &le){ vis[u] = 1; cv[u - 1] = 1; le --; if(le == 0) return; for(auto v : g[u]){ if(vis[v]) continue; dfs1(v, le); if(le == 0) return; } } void dfs2(ll u, ll &le){ vis[u] = 1; cv[u - 1] = 2; le --; if(le == 0) return; for(auto v : g[u]){ if(vis[v]) continue; dfs2(v, le); if(le == 0) return; } } vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> p, vector<int> q) { n = _n, a = _a, b = _b, c = _c; cal[1] = 1, cal[2] = 2, cal[3] = 3; cv.assign(n, 3); if(a > b) swap(a, b), swap(cal[1], cal[2]); if(a > c) swap(a, c), swap(cal[1], cal[3]); if(b > c) swap(b, c), swap(cal[2], cal[3]); for(ll i = 0; i < len(p); i ++){ g[p[i] + 1].pb(q[i] + 1); g[q[i] + 1].pb(p[i] + 1); } ll ch = 0; vector<pll> scc; for(ll qq = 1; qq <= n; qq ++){ vis.reset(); scc.clear(); ll root = qq; for(auto v : g[root]){ if(vis[v]) continue; ll le = dfs(v); scc.pb({le, v}); } sort(all(scc)); for(auto [le, u] : scc){ if(le >= a){ cv.assign(n, 3); vis.reset(); vis[root] = 1; ll tmp = a; dfs1(u, tmp); if(tmp) continue; vis[root] = 0; tmp = b; dfs2(root, tmp); if(tmp) continue; ch = 1; break; } } } if(!ch){ for(ll i = 0; i <= n - 1; i ++) cv[i] = 0; return cv; } for(ll i = 0; i <= n - 1; i ++){ cv[i] = cal[cv[i]]; } return cv; } // void _() { // } // signed main() { // ll tm = clock(); // cin.tie(0)->sync_with_stdio(0); // ll t = 1; // // cin >> t; // for(ll tt = 1; tt <= t; tt ++) _(); // cerr << "\n\033[1;31mTime: \033[1;30m" \ // << (double)(clock()-tm)/1000000 << "\033[1;32m seconds\n"; // }
#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...