이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 1e6 + 9;
const ll inf = INT_MAX;
const ll Log2 = 20;
typedef pair<ll,ll> LL;
vector<ll> g[N];
ll n,a[N],mn = inf,chosen,child[N],InitChild[N],sum;
set<LL> s[N];
void DFSinit(ll u,ll p){
child[u] = a[u];
for (auto i : g[u]){
if (i == p) continue;
DFSinit(i,u); child[u] += child[i];
s[u].insert({child[i],i});
}
InitChild[u] = child[u];
}
void DFS(ll u,ll p){
if (!s[u].empty()){
LL now = *s[u].rbegin(),rm = {sum - child[u],-1};
now = max(now,rm);
if (now.fs < mn) mn = now.fs,chosen = u;
}
for (auto i : g[u]){
if (i == p) continue;
s[u].erase({child[i],i}); s[i].insert({sum - child[i],u});
//cout<<child[i]<<" "<<i; exit(0);
child[u] = sum - child[i]; child[i] = sum;
DFS(i,u);
}
if (p >= 0){
child[u] = InitChild[u];
s[p].insert({child[u],u}); s[u].erase({child[p],p});
child[p] = InitChild[p];
}
}
ll LocateCentre(ll sz,ll P[],ll X[],ll Y[]){
n = sz;
for (ll i = 0;i < n;i++) a[i] = P[i],sum += a[i];
for (ll i = 0;i < n - 1;i++){
g[X[i]].push_back(Y[i]); g[Y[i]].push_back(X[i]);
}
DFSinit(0,-1); DFS(0,-1);
return chosen;
}
/*
ll sz,X[N],Y[N],P[N];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#define task "test"
if (fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
//freopen(task".out", "w", stdout);
}
cin>>sz;
for (ll i = 0;i < sz;i++) cin>>P[i];
for (ll i = 0;i < sz - 1;i++) cin>>X[i]>>Y[i];
cout<<LocateCentre(sz,P,X,Y);
}
*/
컴파일 시 표준 에러 (stderr) 메시지
traffic.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
1 | #pragma GCC optimization "O2"
|
traffic.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
2 | #pragma GCC optimization "unroll-loop"
|
# | 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... |