이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define ll long long
#define f first
#define sc second
#define pb push_back
using namespace std;
ll a,b,c,d,i,e,f,g,n,m,k,l;
ll t,maxroot,fotlebi,wvrt,sum,idx;
pair < pair <ll,ll> , pair <ll,ll> > A[200005];
ll in[200005],out[200005],P[200005],D[200005],down[200005],inv[200005];
ll lz[800005];
pair <ll,ll> tree[800005],pr;
ll ans[200005],fix[200005];
vector < pair < ll, pair <ll,ll> > > v[200005];
void build(ll node,ll le,ll ri) {
lz[node]=0;
if(le==ri) {
tree[node].f=0;
tree[node].sc=le;
return;
}
build(2*node,le,(le+ri)/2);
build(2*node+1,(le+ri)/2+1,ri);
if(tree[2*node].f>tree[2*node+1].f) tree[node]=tree[2*node];
else tree[node]=tree[2*node+1];
}
void update(ll node,ll le,ll ri,ll start,ll end,ll val) {
if(lz[node]) {
tree[node].f+=lz[node];
if(le!=ri) {
lz[2*node]+=lz[node];
lz[2*node+1]+=lz[node];
}
lz[node]=0;
}
if(ri<start || le>end) return;
if(start<=le && ri<=end) {
tree[node].f+=val;
if(le!=ri) {
lz[2*node]+=val;
lz[2*node+1]+=val;
}
return;
}
update(2*node,le,(le+ri)/2,start,end,val);
update(2*node+1,(le+ri)/2+1,ri,start,end,val);
if(tree[2*node].f>tree[2*node+1].f) tree[node]=tree[2*node];
else tree[node]=tree[2*node+1];
}
pair <ll,ll> getmax(ll node,ll le,ll ri,ll start,ll end) {
if(lz[node]) {
tree[node].f+=lz[node];
if(le!=ri) {
lz[2*node]+=lz[node];
lz[2*node+1]+=lz[node];
}
lz[node]=0;
}
if(ri<start || le>end) return {-1,-1};
if(start<=le && ri<=end) { return tree[node]; }
pair <ll,ll> pr1=getmax(2*node,le,(le+ri)/2,start,end);
pair <ll,ll> pr2=getmax(2*node+1,(le+ri)/2+1,ri,start,end);
if(pr1.f>pr2.f) return pr1;
else return pr2;
}
void dfs(ll x,ll y,ll dist) {
//cout<<x<<" "<<y<<" "<<dist<<endl;
t++;
in[x]=t;
D[x]=dist;
P[x]=y;
inv[t]=x;
down[x]=D[x]-D[y];
if(x!=maxroot && v[x].size()==1 && maxroot!=0) fotlebi++;
update(1,1,n,in[x],in[x],D[x]);
//cout<<x<<" "<<in[x]<<" "<<D[x]<<endl;
for(ll i=0;i<v[x].size();i++) {
if(v[x][i].f==y) continue;
dfs(v[x][i].f,x,dist+v[x][i].sc.f);
wvrt+=v[x][i].sc.sc;
}
out[x]=t;
}
void dfs1(ll x,ll y) {
ans[1]=max(ans[1],wvrt);
pr=getmax(1,1,n,1,n);
//cout<<x<<"_"<<wvrt<<"_"<<pr.f<<endl;
if(ans[2]<wvrt+pr.f) { ans[2]=wvrt+pr.f; maxroot=x; }
for(ll i=0;i<v[x].size();i++) {
if(v[x][i].f==y) continue;
ll yx=v[x][i].sc.f; ll xy=v[x][i].sc.sc;
wvrt=wvrt+yx-xy;
update(1,1,n,in[v[x][i].f],out[v[x][i].f],-yx);
update(1,1,n,1,in[v[x][i].f]-1,xy);
update(1,1,n,out[v[x][i].f]+1,n,xy);
dfs1(v[x][i].f,x);
wvrt=wvrt-yx+xy;
update(1,1,n,in[v[x][i].f],out[v[x][i].f],+yx);
update(1,1,n,1,in[v[x][i].f]-1,-xy);
update(1,1,n,out[v[x][i].f]+1,n,-xy);
}
}
int main() {
std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
for(ll i=1;i<n;i++) {
cin>>A[i].f.f>>A[i].f.sc>>A[i].sc.f>>A[i].sc.sc;
v[A[i].f.f].pb({A[i].f.sc,{A[i].sc.f,A[i].sc.sc}});
v[A[i].f.sc].pb({A[i].f.f,{A[i].sc.sc,A[i].sc.f}});
sum+=A[i].sc.f+A[i].sc.sc;
}
build(1,1,n);
dfs(1,0,0);
//cout<<"*"; return 0;
dfs1(1,0);
build(1,1,n);
t=0;
//cout<<maxroot<<endl;
dfs(maxroot,0,0);
for(ll i=2;i<=fotlebi+1;i++) {
pr=getmax(1,1,n,1,n);
if(i!=2) ans[i]=ans[i-1]+pr.f;
//cout<<ans[i]<<" ";
idx=inv[pr.sc];
//cout<<pr.f<<" "<<pr.sc<<" "<<idx<<endl;
while(idx!=maxroot && fix[idx]==0) {
fix[idx]=1;
update(1,1,n,in[idx],out[idx],-down[idx]);
idx=P[idx];
}
}
cin>>t;
while(t--) {
cin>>f;
if(f>fotlebi) cout<<0<<endl;
else cout<<sum-ans[f]<<endl;
}
}
/*
4
1 2 1 2
1 3 3 4
1 4 5 6
2
1
2
*/
컴파일 시 표준 에러 (stderr) 메시지
designated_cities.cpp: In function 'void dfs(long long int, long long int, long long int)':
designated_cities.cpp:77:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(ll i=0;i<v[x].size();i++) {
| ~^~~~~~~~~~~~
designated_cities.cpp: In function 'void dfs1(long long int, long long int)':
designated_cities.cpp:89:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for(ll i=0;i<v[x].size();i++) {
| ~^~~~~~~~~~~~
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |