Submission #378170

#	Time	Username	Problem	Language	Result	Execution time	Memory
378170		daniel920712	Designated Cities (JOI19_designated_cities)	C++14	16 / 100	1198 ms	161076 KiB

designated_cities

#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 all2[200005];
long long xx[200005];
long long how[200005];
long long who[200005];
long long Father[200005];
long long l,r,now2=0;
long long ll[200005],rr[200005];
long long N=0,big=1e18;
long long x,y,root,now=1;
pair < long long , long long > A,B;
struct A
{
    long long here,l,r,add;
    long long nxl,nxr;
    pair < long long , long long > ans;
}Node[1000005];
void build(long long l,long long r,long long here)
{
    Node[here].l=l;
    Node[here].r=r;
    Node[here].add=0;
    if(l==r)
    {
        //printf("tt %lld %lld %lld\n",l,all2[l],who[l]);
        Node[here].ans=make_pair(all2[l],who[l]);
        return;
    }
    Node[here].nxl=now++;
    Node[here].nxr=now++;
    build(l,(l+r)/2,Node[here].nxl);
    build((l+r)/2+1,r,Node[here].nxr);
    Node[here].ans=max(Node[Node[here].nxl].ans,Node[Node[here].nxr].ans);
}
void UPD(long long here)
{
    Node[Node[here].nxl].ans.first+=Node[here].add;
    Node[Node[here].nxr].ans.first+=Node[here].add;
    Node[Node[here].nxl].add+=Node[here].add;
    Node[Node[here].nxr].add+=Node[here].add;
    Node[here].add=0;
    return;
}
void cha(long long l,long long r,long long con,long long here)
{
    if(l==Node[here].l&&r==Node[here].r)
    {
        //printf("%lld %lld %lld\n",l,r,con);
        Node[here].ans.first+=con;
        return;
    }
    UPD(here);
    if(r<=(Node[here].l+Node[here].r)/2) cha(l,r,con,Node[here].nxl);
    else if(l>(Node[here].l+Node[here].r)/2) cha(l,r,con,Node[here].nxr);
    else
    {
        cha(l,(Node[here].l+Node[here].r)/2,con,Node[here].nxl);
        cha((Node[here].l+Node[here].r)/2+1,r,con,Node[here].nxr);
    }
    Node[here].ans=max(Node[Node[here].nxl].ans,Node[Node[here].nxr].ans);
}
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);
    big=max(big,con);
    if(big==con) x=here;
}
void F5(long long here)
{
    long long ok=0;
    //printf("%lld %lld\n",here,Father[here]);
    if(Father[here]==-1||all[Father[here]].find(here)==all[Father[here]].end()) return;
    cha(ll[here],rr[here],0-all[Father[here]][here],0);
    //printf("%lld %lld\n",ll[here],rr[here]);
    //printf("%lld %lld %lld %lld\n",here,0-all[Father[here]][here],ll[here],rr[here]);
    all[Father[here]].erase(here);
    F5(Father[here]);
}
void F6(long long here,long long fa,long long con)
{
    all2[now2]=con;
    ll[here]=now2;
    Father[here]=fa;
    who[now2]=here;

    for(auto i:Next[here])
    {
        if(i.first==fa) continue;
        now2++;
        F6(i.first,here,con+i.second);
    }
    rr[here]=now2;
    //printf("%lld %lld %lld\n",here,ll[here],rr[here]);
}
int main()
{
    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);
    F6(root,-1,0);
    build(0,N-1,0);
    //printf("aa %lld %lld %lld\n",root,x,y);
    //printf("%lld\n",Node[0].ans.first);
    F5(x);
    //printf("%lld\n",Node[0].ans.first);
    F5(y);
    //printf("%lld\n",Node[0].ans.first);

    how[2]=big;
    for(i=3;i<=N;i++)
    {
        x=Node[0].ans.second;
        //printf("bb %lld %lld\n",x,Node[0].ans.first);
        how[i]=how[i-1]-Node[0].ans.first;
        F5(x);
    }
    scanf("%lld",&M);
    while(M--)
    {
        scanf("%lld",&a);
        printf("%lld\n",how[a]);
    }

    return 0;
}

Compilation message (stderr)

designated_cities.cpp: In function 'void F3(long long int, long long int, long long int)':
designated_cities.cpp:122:36: warning: variable 'a' set but not used [-Wunused-but-set-variable]
  122 |     pair < long long , long long > a=make_pair(con,here),tt;
      |                                    ^
designated_cities.cpp: In function 'void F5(long long int)':
designated_cities.cpp:129:15: warning: unused variable 'ok' [-Wunused-variable]
  129 |     long long ok=0;
      |               ^~
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:156:19: warning: unused variable 'j' [-Wunused-variable]
  156 |     long long M,i,j,k,a,b,c,d,where;
      |                   ^
designated_cities.cpp:156:21: warning: unused variable 'k' [-Wunused-variable]
  156 |     long long M,i,j,k,a,b,c,d,where;
      |                     ^
designated_cities.cpp:156:31: warning: variable 'where' set but not used [-Wunused-but-set-variable]
  156 |     long long M,i,j,k,a,b,c,d,where;
      |                               ^~~~~
designated_cities.cpp:157:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  157 |     scanf("%lld",&N);
      |     ~~~~~^~~~~~~~~~~
designated_cities.cpp:160:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  160 |         scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:193:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  193 |     scanf("%lld",&M);
      |     ~~~~~^~~~~~~~~~~
designated_cities.cpp:196:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  196 |         scanf("%lld",&a);
      |         ~~~~~^~~~~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44