제출 #1047690

#제출 시각아이디문제언어결과실행 시간메모리
1047690efedmrlrSplit the Attractions (IOI19_split)C++17
40 / 100
427 ms1048576 KiB
// #pragma GCC optimize("O3,Ofast,unroll-loops") // #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include <bits/stdc++.h> #include "split.h" using namespace std; #define lli long long int #define MP make_pair #define pb push_back #define REP(i,n) for(int i = 0; (i) < (n); (i)++) #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() const double EPS = 0.00001; const int INF = 1e9+500; const int ALPH = 26; const int LGN = 25; constexpr int MOD = 1e9+7; using namespace std; vector<vector<int> > adj; vector<int> pr, sub; vector<array<int, 2> > ord(3); vector<int> ans; int m, N; vector<int> spl(2, -1); void dfs(int node, int par) { pr[node] = par; sub[node] = 1; for(auto c : adj[node]) { if(c == pr[node]) continue; dfs(c, node); sub[node] += sub[c]; } if(spl[0] != -1) return; vector<int> szs = {N - sub[node], sub[node]}; bool swa = 0; if(szs[0] > szs[1]) { swa = 1; swap(szs[0], szs[1]); } // cout << "node: " << node << " p:" << pr[node] << " sub:" << sub[node] << " sz0:" << szs[0] << " sz1: " << szs[1] << "\n"; if(szs[0] >= ord[0][0] && szs[1] >= ord[1][0]) { spl[0] = 0; spl[1] = node; if(swa) swap(spl[0], spl[1]); } } int cnt = 0; void dfs2(int node, int forb, int num) { if(node == forb || cnt == ord[num][0]) return; cnt++; ans[node] = ord[num][1]; for(auto c : adj[node]) { if(c == pr[node]) continue; dfs2(c, forb, num); } } array<int, 2> cycle_dfs(int node, int start, int cur, int par) { if(cnt == ord[cur][0] || node == start) { return {node, par}; } ans[node] = ord[cur][1]; cnt++; for(auto c : adj[node]) { if(c == par) continue; return cycle_dfs(c, start, cur, node); } } void solve_cycle() { cnt = 1; ans[0] = ord[0][1]; auto last = cycle_dfs(adj[0][0], 0, 0, 0); cnt = 0; last = cycle_dfs(last[0], 0, 1, last[1]); cnt = 0; last = cycle_dfs(last[0], 0, 2, last[1]); } vector<int> vis; void dfs3(int node, int num) { if(vis[node] || cnt == ord[num][0]) return; cnt++; vis[node] = 1; ans[node] = ord[num][1]; for(auto c : adj[node]) { dfs3(c, num); } } void solve_a1() { cnt = 0; vis.assign(N , 0); dfs3(0, 1); bool f = 0; REP(i, N) { if(ans[i] != 0) continue; if(f) { ans[i] = ord[2][1]; } else { ans[i] = ord[0][1]; f = 1; } } } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { adj.assign(n, vector<int>()); ans.assign(n, 0); sub.assign(n, 0); spl.assign(2, -1); ord.resize(3); ord[0] = {a, 1}; ord[1] = {b, 2}; ord[2] = {c, 3}; sort(all(ord)); N = n; pr.assign(n, 0); m = (int)p.size(); int mxx = 1; for(int i = 0; i < m; i++) { adj[p[i]].pb(q[i]); adj[q[i]].pb(p[i]); } REP(i, n) { if((int)adj[i].size() != 2) mxx = 0; } if(mxx) { solve_cycle(); return ans; } if(a == 1) { solve_a1(); return ans; } dfs(0, 0); if(spl[0] == -1) { return ans; } cnt = 0; dfs2(spl[0], spl[1], 0); cnt = 0; dfs2(spl[1], spl[0], 1); REP(i, n) { if(ans[i] == 0) ans[i] = ord[2][1]; } return ans; }

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

split.cpp: In function 'std::array<int, 2> cycle_dfs(int, int, int, int)':
split.cpp:77:1: warning: control reaches end of non-void function [-Wreturn-type]
   77 | }
      | ^
#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...