제출 #1256285

#제출 시각아이디문제언어결과실행 시간메모리
1256285nerrrminSplit the Attractions (IOI19_split)C++20
18 / 100
57 ms21964 KiB
#include "split.h" #define pb push_back #include<bits/stdc++.h> using namespace std; const int maxn = 3e5 + 10; int m, deg[maxn]; vector < int > g[maxn]; int used[maxn]; int sub[maxn], par[maxn], ver = 0, all; int in, out; int c1, c2, c3; int col1, col2, col3; void dfs(int beg, int from) { used[beg] = 1; sub[beg] = 1; for (auto nb: g[beg]) { if(used[nb])continue; if(nb == from)continue; dfs(nb, beg); par[nb] = beg; sub[beg] += sub[nb]; } if(sub[beg] >= c1 && all-sub[beg] >= c1) { if(out < all - sub[beg]) {ver = beg; in = sub[beg]; out = all-sub[beg]; } } } int track[maxn]; int broika; void rec(int beg, int from, int cvqt) { if(!broika)return; broika --; track[beg] = cvqt; //cout << "gtt " << endl; for (auto nb: g[beg]) { if(nb == from)continue; if(track[nb])continue; rec(nb, beg, cvqt); } } int cnt = 0; void rec2(int beg, int from, int cvqt) { if(track[beg])return; cnt ++; if(!broika)return; broika --; track[beg] = cvqt; for (auto nb: g[beg]) { if(nb == from)continue; if(track[nb])continue; rec2(nb, beg, cvqt); } } vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) { m = p.size(); all = n; ver = -1; for (int i = 0; i < m; ++ i) { g[p[i]].pb(q[i]); g[q[i]].pb(p[i]); } if(a <= min(b, c)) { c1 = a; col1 = 1; } else if(b <= min(a, c)) { c1 = b; col1 = 2; } else if(c <= min(a, b)) { c1 = c; col1 = 3; } if(1 != col1 && a >= max(b, c)) { c3 = a; col3 = 1; } else if(2 != col1 && b >= max(a, c)) { c3 = b; col3 = 2; } else if(3 != col1 && c >= max(a, b)) { c3 = c; col3 = 3; } col2 = 6 - col1 - col3; c2 = n - c1 - c3; assert(c1 + c2 + c3 == n); assert(col1 >= 1 && col1 <= 3); assert(col2 >= 1 && col2 <= 3); assert(col3 >= 1 && col3 <= 3); dfs(0, -1); vector < int > ans; if(ver == -1) { for (int i = 1; i <= n; ++ i) ans.pb(0); return ans; } int pos = ver; if(out >= c2) { broika = c1; rec(ver, par[pos], col1); broika = c2; rec2(par[pos], -1, col2); for (int j = 0; j < n; ++ j) if(track[j] == 0)track[j] = col3; for (int j = 0; j < n; ++ j) ans.pb(track[j]); return ans; } }

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

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