이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "split.h"
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
//#define int ll
#define ve vector
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
#define fpp(a,i,c) for(int (a) = (i); (a) <= (c); (a)++)
#define fv(a, c) for(int (a) = (1); (a) <= (c); (a)++)
#define fz(a, c) for(int (a) = (0); (a) < (c); (a)++)
#define fm(a,i,c) for(int (a) = (i); (a) > (c); (a)--)
#define fmm(a,i,c) for(int (a) = (i); (a) >= (c); (a)--)
#define pb push_back
#define in insert
#define ss second
#define ff first
#define vi vector <int>
#define fa(a, v) for(int (a) : (v))
#define mnel(a) *min_element(all(a))
#define mxel(a) *max_element(all(a))
#define si set<int>
#define sov(a) sort(all((a)))
ve<vi> G, C;
vi num, siz, low;
int n, x;
pii X, Y, Z;
bool found = 0, sol = 0;
tuple<int, int, int> top ,bottom;
vector <bool> B;
void dfs (int u, int p){
siz[u] = 1;
x ++;
num[u] = x;
low[u] = x;
bool ok = 1;
fa(v, G[u]){
if(num[v] == 0){
dfs(v, u);
siz[u] += siz[v];
low[u] = min(low[v], low[u]);
if(siz[v] >= X.ff)
ok = 0;
C[u].pb(v);
}
else
if(v != p)
low[u] = min(low[u], num[v]);
}
if(siz[u] < X.ff)
ok = 0;
if(ok && !found){
found = 1;
int cur = siz[u];
fa(v, C[u]){
if(low[v] < num[u]){
if(cur - siz[v] >= X.ff){
B[v] = 1;
cur -= siz[v];
}
}
}
int opt = n - cur;
if(opt >= Y.ff){
sol = 1;
top = {Y.ff, Y.ss, p};
bottom = {X.ff, X.ss, u};
}
else
if(opt >= X.ff){
sol = 1;
top = {X.ff, X.ss, p};
bottom = {Y.ff, Y.ss, u};
}
}
}
vector<int> find_split(int nn, int a, int b, int c, vector<int> p, vector<int> q) {
vi ans(n);
int m = p.size();
n = nn;
G = ve<vi> (n);
C = ve<vi> (n);
num = vi (n);
siz = vi (n);
low = vi (n);
B = ve<bool> (n);
queue <int> Q;
fp(i,0,m){
G[p[i]].pb(q[i]);
G[q[i]].pb(p[i]);
}
ve<pii> A = {{a, 1}, {b, 2}, {c, 3}};
sort(all(A));
X = A[0], Y = A[1], Z = A[2];
dfs(0, -1);
if(sol){
ans = vi (n, Z.ss);
int sz, d, s;
tie(sz, d, s) = bottom;
ans[s] = d;
sz --;
Q.push(s);
while(Q.size()){
int u = Q.front();
Q.pop();
fa(v, C[u]){
if(!B[v]){
if(sz > 0){
ans[v] = d;
Q.push(v);
sz --;
}
}
}
}
tie(sz, d, s) = top;
ans[s] = d;
sz--;
Q.push(s);
while(Q.size()){
int u = Q.front();
Q.pop();
fa(v, G[u]){
if(ans[v] == Z.ss){
if(sz > 0){
sz--;
ans[v] = d;
Q.push(v);
}
}
}
}
}
else
ans = vi (n);
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
split.cpp: In function 'void dfs(int, int)':
split.cpp:26:26: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
26 | #define fa(a, v) for(int (a) : (v))
| ^
split.cpp:47:5: note: in expansion of macro 'fa'
47 | fa(v, G[u]){
| ^~
split.cpp:26:26: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
26 | #define fa(a, v) for(int (a) : (v))
| ^
split.cpp:66:9: note: in expansion of macro 'fa'
66 | fa(v, C[u]){
| ^~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
15 | #define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
| ^
split.cpp:103:5: note: in expansion of macro 'fp'
103 | fp(i,0,m){
| ^~
split.cpp:26:26: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
26 | #define fa(a, v) for(int (a) : (v))
| ^
split.cpp:122:13: note: in expansion of macro 'fa'
122 | fa(v, C[u]){
| ^~
split.cpp:26:26: warning: unnecessary parentheses in declaration of 'v' [-Wparentheses]
26 | #define fa(a, v) for(int (a) : (v))
| ^
split.cpp:140:13: note: in expansion of macro 'fa'
140 | fa(v, G[u]){
| ^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |