Submission #378109

#	Time	Username	Problem	Language	Result	Execution time	Memory
378109		daniel920712	Designated Cities (JOI19_designated_cities)	C++14	23 / 100	2080 ms	62188 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 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)

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

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