# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
378109 | daniel920712 | Designated Cities (JOI19_designated_cities) | C++14 | 2080 ms | 62188 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <set>
using namespace std;
vector < pair < long long , long long > > Next[200005];
map < long long , long long > all[200005];
set < long long > vis[200005];
long long ans[200005];
long long xx[200005];
long long how[200005];
long long N=0,big=1e18;
long long x,y,root;
pair < long long , long long > A,B;
void F(long long here,long long fa)
{
for(auto i:Next[here])
{
if(i.first!=fa)
{
ans[1]+=i.second;
F(i.first,here);
}
}
}
void F2(long long here,long long fa)
{
for(auto i:Next[here])
{
if(i.first!=fa)
{
ans[i.first]=ans[here]-all[here][i.first]+all[i.first][here];
F2(i.first,here);
}
}
}
pair < long long , long long > F4(long long here,long long fa,long long con)
{
pair < long long , long long > a=make_pair(con,here),b=make_pair(con,here),tt;
for(auto i:Next[here])
{
if(i.first!=fa)
{
tt=F4(i.first,here,con+i.second);
if(tt>a)
{
b=a;
a=tt;
}
else if(tt>b) b=tt;
}
}
big=min(big,ans[here]-(a.first+b.first-2*con));
if(big==ans[here]-(a.first+b.first-2*con))
{
root=here;
x=a.second;
y=b.second;
}
return a;
}
void F3(long long here,long long fa,long long con)
{
pair < long long , long long > a=make_pair(con,here),tt;
for(auto i:Next[here])
{
if(i.first!=fa)
{
F3(i.first,here,con+i.second);
//if(tt>a) a=tt;
}
}
big=max(big,con);
if(big==con) x=here;
//return a;
}
bool F5(long long here,long long fa)
{
//vector < pair < long long , long long > > del;
long long ok=0;
if(here==x||here==y) ok=1;
for(auto &i:Next[here])
{
if(i.first==fa) continue;
if(F5(i.first,here))
{
//printf("bb %lld %lld\n",here,i.first);
//all[here][i.first]=0;
i.second=0;
ok=1;
}
}
return ok;
}
int main()
{
//freopen("01-04.txt","rt",stdin);
long long M,i,j,k,a,b,c,d,where;
scanf("%lld",&N);
for(i=1;i<N;i++)
{
scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
Next[a].push_back(make_pair(b,c));
Next[b].push_back(make_pair(a,d));
all[a][b]=c;
all[b][a]=d;
}
for(i=1;i<=N;i++) xx[i]=1e18;
F(1,-1);
F2(1,-1);
how[1]=1e18;
for(i=1;i<=N;i++)
{
how[1]=min(how[1],ans[i]);
if(how[1]==ans[i]) where=i;
}
F4(1,-1,0);
//printf("%lld %lld %lld\n",root,x,y);
F5(root,-1);
how[2]=big;
for(i=3;i<=N;i++)
{
y=-1;
big=0;
F3(root,-1,0);
//printf("aa %lld %lld\n",big,x);
how[i]=how[i-1]-big;
F5(root,-1);
}
scanf("%lld",&M);
while(M--)
{
scanf("%lld",&a);
printf("%lld\n",how[a]);
}
return 0;
}
Compilation message (stderr)
# | 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... |