oj.uz

Submission #378106

# Submission time Handle Problem Language Result Execution time Memory
378106 2021-03-16T02:48:21 Z daniel920712 Designated Cities (JOI19_designated_cities) C++14
22 / 100
 671 ms 95340 KB 
#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;
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);
        }
    }
}
void F3(long long here,long long fa)
{
    for(auto i:Next[here])
    {
        if(i.first!=fa)
        {
            vis[here].insert(i.first);
            F3(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;
            }
        }
    }
    //printf("%lld %lld %lld %lld %lld\n",here,how[here],a.first,b.first,con);
    big=min(big,ans[here]-(a.first+b.first-2*con));
    return a;
}
int main()
{
    //freopen("03-02.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;
    if(N<=16)
    {
        for(i=0;i<(1<<N);i++)
        {
            a=0;
            b=0;
            for(j=1;j<=N;j++) vis[j].clear();
            for(j=0;j<N;j++)
            {
                if(i&(1<<j))
                {
                    F3(j+1,-1);
                    a++;
                }
            }
            for(j=1;j<=N;j++) for(auto k:Next[j]) if(vis[j].find(k.first)==vis[j].end()) b+=all[k.first][j];
            xx[a]=min(xx[a],b);
        }
        scanf("%lld",&M);
        while(M--)
        {
            scanf("%lld",&a);
            printf("%lld\n",xx[a]);
        }
    }
    else
    {
        F(1,-1);
        F2(1,-1);
        how[1]=1e18;
        for(i=1;i<=N;i++)
        {
            //printf("%lld\n",ans[i]);
            how[1]=min(how[1],ans[i]);
            if(how[1]==ans[i]) where=i;
        }
        F4(1,-1,0);
        how[2]=big;
        scanf("%lld",&M);
        while(M--)
        {
            scanf("%lld",&a);
            //printf("%lld\n",a);
            printf("%lld\n",how[a]);
        }
    }
    return 0;
}

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:76:21: warning: unused variable 'k' [-Wunused-variable]
   76 |     long long M,i,j,k,a,b,c,d,where;
      |                     ^
designated_cities.cpp:76:31: warning: variable 'where' set but not used [-Wunused-but-set-variable]
   76 |     long long M,i,j,k,a,b,c,d,where;
      |                               ^~~~~
designated_cities.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   77 |     scanf("%lld",&N);
      |     ~~~~~^~~~~~~~~~~
designated_cities.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |         scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  105 |         scanf("%lld",&M);
      |         ~~~~~^~~~~~~~~~~
designated_cities.cpp:108:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  108 |             scanf("%lld",&a);
      |             ~~~~~^~~~~~~~~~~
designated_cities.cpp:125:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  125 |         scanf("%lld",&M);
      |         ~~~~~^~~~~~~~~~~
designated_cities.cpp:128:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  128 |             scanf("%lld",&a);
      |             ~~~~~^~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 198 ms 23916 KB Output is correct
3 Correct 189 ms 23916 KB Output is correct
4 Correct 195 ms 23788 KB Output is correct
5 Correct 194 ms 24044 KB Output is correct
6 Correct 212 ms 23916 KB Output is correct
7 Correct 187 ms 23788 KB Output is correct
8 Correct 209 ms 23924 KB Output is correct
9 Correct 192 ms 23916 KB Output is correct
10 Correct 186 ms 23788 KB Output is correct
11 Correct 206 ms 23788 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 529 ms 62572 KB Output is correct
3 Correct 558 ms 85484 KB Output is correct
4 Correct 512 ms 62460 KB Output is correct
5 Correct 540 ms 62564 KB Output is correct
6 Correct 554 ms 65772 KB Output is correct
7 Correct 607 ms 62176 KB Output is correct
8 Correct 567 ms 86252 KB Output is correct
9 Correct 662 ms 62028 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 528 ms 62664 KB Output is correct
3 Correct 572 ms 95340 KB Output is correct
4 Correct 523 ms 67308 KB Output is correct
5 Correct 567 ms 68732 KB Output is correct
6 Correct 553 ms 72428 KB Output is correct
7 Correct 654 ms 67668 KB Output is correct
8 Correct 579 ms 83692 KB Output is correct
9 Correct 671 ms 67540 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 198 ms 23916 KB Output is correct
3 Correct 189 ms 23916 KB Output is correct
4 Correct 195 ms 23788 KB Output is correct
5 Correct 194 ms 24044 KB Output is correct
6 Correct 212 ms 23916 KB Output is correct
7 Correct 187 ms 23788 KB Output is correct
8 Correct 209 ms 23924 KB Output is correct
9 Correct 192 ms 23916 KB Output is correct
10 Correct 186 ms 23788 KB Output is correct
11 Correct 206 ms 23788 KB Output is correct
12 Correct 16 ms 23788 KB Output is correct
13 Incorrect 19 ms 24300 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 529 ms 62572 KB Output is correct
3 Correct 558 ms 85484 KB Output is correct
4 Correct 512 ms 62460 KB Output is correct
5 Correct 540 ms 62564 KB Output is correct
6 Correct 554 ms 65772 KB Output is correct
7 Correct 607 ms 62176 KB Output is correct
8 Correct 567 ms 86252 KB Output is correct
9 Correct 662 ms 62028 KB Output is correct
10 Correct 16 ms 23788 KB Output is correct
11 Correct 528 ms 62664 KB Output is correct
12 Correct 572 ms 95340 KB Output is correct
13 Correct 523 ms 67308 KB Output is correct
14 Correct 567 ms 68732 KB Output is correct
15 Correct 553 ms 72428 KB Output is correct
16 Correct 654 ms 67668 KB Output is correct
17 Correct 579 ms 83692 KB Output is correct
18 Correct 671 ms 67540 KB Output is correct
19 Correct 16 ms 23788 KB Output is correct
20 Incorrect 577 ms 68716 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 198 ms 23916 KB Output is correct
3 Correct 189 ms 23916 KB Output is correct
4 Correct 195 ms 23788 KB Output is correct
5 Correct 194 ms 24044 KB Output is correct
6 Correct 212 ms 23916 KB Output is correct
7 Correct 187 ms 23788 KB Output is correct
8 Correct 209 ms 23924 KB Output is correct
9 Correct 192 ms 23916 KB Output is correct
10 Correct 186 ms 23788 KB Output is correct
11 Correct 206 ms 23788 KB Output is correct
12 Correct 16 ms 23788 KB Output is correct
13 Correct 529 ms 62572 KB Output is correct
14 Correct 558 ms 85484 KB Output is correct
15 Correct 512 ms 62460 KB Output is correct
16 Correct 540 ms 62564 KB Output is correct
17 Correct 554 ms 65772 KB Output is correct
18 Correct 607 ms 62176 KB Output is correct
19 Correct 567 ms 86252 KB Output is correct
20 Correct 662 ms 62028 KB Output is correct
21 Correct 16 ms 23788 KB Output is correct
22 Correct 528 ms 62664 KB Output is correct
23 Correct 572 ms 95340 KB Output is correct
24 Correct 523 ms 67308 KB Output is correct
25 Correct 567 ms 68732 KB Output is correct
26 Correct 553 ms 72428 KB Output is correct
27 Correct 654 ms 67668 KB Output is correct
28 Correct 579 ms 83692 KB Output is correct
29 Correct 671 ms 67540 KB Output is correct
30 Correct 16 ms 23788 KB Output is correct
31 Incorrect 19 ms 24300 KB Output isn't correct
32 Halted 0 ms 0 KB -