제출 #899513

#제출 시각아이디문제언어결과실행 시간메모리
899513rxlfd314Split the Attractions (IOI19_split)C++17
40 / 100
78 ms16504 KiB
#include "split.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using ari2 = array<int, 2>; using ari3 = array<int, 3>; #define vt vector #define size(x) (int((x).size())) #define all(x) begin(x), end(x) #define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d)) #define FOR(a, b, c) REP(a, b, c, 1) #define ROF(a, b, c) REP(a, b, c, -1) vt<int> find_split(int N, int X, int Y, int Z, vt<int> P, vt<int> Q) { ari2 A = {X, 1}, B = {Y, 2}, C = {Z, 3}; if (B > C) swap(B, C); if (A > B) swap(A, B); if (B > C) swap(B, C); vt<int> adj[N]; bool sub1 = true; FOR(i, 0, size(P)-1) { adj[P[i]].push_back(Q[i]); adj[Q[i]].push_back(P[i]); sub1 &= size(adj[P[i]]) < 3 && size(adj[Q[i]]) < 3; } if (sub1) { int s = 0; FOR(i, 0, N-1) if (size(adj[i]) == 1) s = i; int cur = s, p = s; vt<int> ans(N, C[1]); while (A[0]--) { ans[cur] = A[1]; for (int i : adj[cur]) if (i != p) { p = cur; cur = i; break; } } while (B[0]--) { ans[cur] = B[1]; for (int i : adj[cur]) if (i != p) { p = cur; cur = i; break; } } return ans; } if (size(P) == N-1) { #ifdef DEBUG cout << "LOL\n"; #endif int szs[N]; function<int(int, int)> calc_sizes = [&](int i, int p) { #ifdef DEBUG cout << "cs: " << i << '\n'; #endif szs[i] = 1; for (int j : adj[i]) if (j != p) szs[i] += calc_sizes(j, i); return szs[i]; }; calc_sizes(0, 0); function<void(int, int, ari2&, vt<int>&)> dfs = [&](int i, int p, ari2 &v, vt<int> &ans) { #ifdef DEBUG cout << "dfs: " << i << '\n'; #endif if (!v[0]) return; ans[i] = v[1]; v[0]--; for (int j : adj[i]) if (j != p) dfs(j, i, v, ans); }; vt<int> ans(N, C[1]); bool found = false; function<void(int, int)> reroot = [&](int i, int p) { if (found) return; #ifdef DEBUG cout << "reroot " << i << '\n'; #endif for (int j : adj[i]) if (szs[i] - szs[j] >= A[0] && szs[j] >= B[0]) { dfs(i, j, A, ans); dfs(j, i, B, ans); found = true; return; } for (int j : adj[i]) if (j != p) { int x = szs[j]; szs[j] = N; szs[i] -= x; reroot(j, i); szs[i] += x; szs[j] = x; } }; reroot(0, 0); if (found) return ans; return vt<int>(N, 0); } if (A[0] == 1) { bool seen[N] = {}; int cnt = A[0] + B[0]; function<void(int)> dfs = [&](int i) { if (seen[i] || !cnt) return; seen[i] = true; cnt--; for (int j : adj[i]) dfs(j); }; dfs(0); vt<int> adj2[N]; FOR(i, 0, N-1) if (seen[i]) { #ifdef DEBUG cout << i << ' '; #endif for (int j : adj[i]) if (seen[j]) adj2[i].push_back(j); } #ifdef DEBUG cout << '\n'; #endif int tin[N], low[N], timer = 0; memset(tin, -1, sizeof(tin)); bool bad[N] = {}; function<void(int, int)> dfs2 = [&](int i, int p) { low[i] = tin[i] = timer++; for (int j : adj2[i]) { if (j == p || !seen[j]) continue; if (~tin[j]) low[i] = min(low[i], tin[j]); else { dfs2(j, i); low[i] = min(low[i], low[j]); if (tin[i] <= low[j] && ~p) { bad[i] = true; } } } if (p < 0 && size(adj2[i]) > 1) bad[i] = true; }; FOR(r, 0, N-1) if (seen[r]) { dfs2(r, -1); vt<int> ans(N, C[1]); int special; FOR(i, 0, N-1) if (seen[i]) { ans[i] = B[1]; if (!bad[i]) special = i; } #ifdef DEBUG cout << "special node " << special << '\n'; #endif ans[special] = A[1]; return ans; } } }

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

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:180:1: warning: control reaches end of non-void function [-Wreturn-type]
  180 | }
      | ^
split.cpp:176:20: warning: 'special' may be used uninitialized in this function [-Wmaybe-uninitialized]
  176 |         ans[special] = A[1];
      |                    ^
#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...