oj.uz

Submission #378084

# Submission time Handle Problem Language Result Execution time Memory
378084 2021-03-16T01:58:50 Z daniel920712 Designated Cities (JOI19_designated_cities) C++14
13 / 100
 644 ms 86080 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=0;
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;
            }
        }
    }
    big=max(big,a.first+b.first-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++)
        {
            how[1]=min(how[1],ans[i]);
            if(how[1]==ans[i]) where=i;
        }
        F4(where,-1,0);
        how[2]=how[1]-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:75:21: warning: unused variable 'k' [-Wunused-variable]
   75 |     long long M,i,j,k,a,b,c,d,where;
      |                     ^
designated_cities.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   76 |     scanf("%lld",&N);
      |     ~~~~~^~~~~~~~~~~
designated_cities.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   79 |         scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:104:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  104 |         scanf("%lld",&M);
      |         ~~~~~^~~~~~~~~~~
designated_cities.cpp:107:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  107 |             scanf("%lld",&a);
      |             ~~~~~^~~~~~~~~~~
designated_cities.cpp:123:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  123 |         scanf("%lld",&M);
      |         ~~~~~^~~~~~~~~~~
designated_cities.cpp:126:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  126 |             scanf("%lld",&a);
      |             ~~~~~^~~~~~~~~~~
designated_cities.cpp:121:22: warning: 'where' may be used uninitialized in this function [-Wmaybe-uninitialized]
  121 |         F4(where,-1,0);
      |                      ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23788 KB Output is correct
2 Correct 208 ms 23788 KB Output is correct
3 Correct 186 ms 23872 KB Output is correct
4 Correct 212 ms 23788 KB Output is correct
5 Correct 196 ms 23916 KB Output is correct
6 Correct 194 ms 23788 KB Output is correct
7 Correct 191 ms 23788 KB Output is correct
8 Correct 201 ms 23916 KB Output is correct
9 Correct 189 ms 23788 KB Output is correct
10 Correct 176 ms 24024 KB Output is correct
11 Correct 203 ms 23788 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23788 KB Output is correct
2 Correct 504 ms 62188 KB Output is correct
3 Correct 570 ms 85228 KB Output is correct
4 Correct 518 ms 62420 KB Output is correct
5 Correct 626 ms 62180 KB Output is correct
6 Correct 523 ms 65492 KB Output is correct
7 Correct 613 ms 61660 KB Output is correct
8 Correct 556 ms 86080 KB Output is correct
9 Correct 644 ms 61436 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23788 KB Output is correct
2 Incorrect 511 ms 62316 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23788 KB Output is correct
2 Correct 208 ms 23788 KB Output is correct
3 Correct 186 ms 23872 KB Output is correct
4 Correct 212 ms 23788 KB Output is correct
5 Correct 196 ms 23916 KB Output is correct
6 Correct 194 ms 23788 KB Output is correct
7 Correct 191 ms 23788 KB Output is correct
8 Correct 201 ms 23916 KB Output is correct
9 Correct 189 ms 23788 KB Output is correct
10 Correct 176 ms 24024 KB Output is correct
11 Correct 203 ms 23788 KB Output is correct
12 Correct 18 ms 23788 KB Output is correct
13 Incorrect 17 ms 24172 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23788 KB Output is correct
2 Correct 504 ms 62188 KB Output is correct
3 Correct 570 ms 85228 KB Output is correct
4 Correct 518 ms 62420 KB Output is correct
5 Correct 626 ms 62180 KB Output is correct
6 Correct 523 ms 65492 KB Output is correct
7 Correct 613 ms 61660 KB Output is correct
8 Correct 556 ms 86080 KB Output is correct
9 Correct 644 ms 61436 KB Output is correct
10 Correct 18 ms 23788 KB Output is correct
11 Incorrect 511 ms 62316 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23788 KB Output is correct
2 Correct 208 ms 23788 KB Output is correct
3 Correct 186 ms 23872 KB Output is correct
4 Correct 212 ms 23788 KB Output is correct
5 Correct 196 ms 23916 KB Output is correct
6 Correct 194 ms 23788 KB Output is correct
7 Correct 191 ms 23788 KB Output is correct
8 Correct 201 ms 23916 KB Output is correct
9 Correct 189 ms 23788 KB Output is correct
10 Correct 176 ms 24024 KB Output is correct
11 Correct 203 ms 23788 KB Output is correct
12 Correct 14 ms 23788 KB Output is correct
13 Correct 504 ms 62188 KB Output is correct
14 Correct 570 ms 85228 KB Output is correct
15 Correct 518 ms 62420 KB Output is correct
16 Correct 626 ms 62180 KB Output is correct
17 Correct 523 ms 65492 KB Output is correct
18 Correct 613 ms 61660 KB Output is correct
19 Correct 556 ms 86080 KB Output is correct
20 Correct 644 ms 61436 KB Output is correct
21 Correct 18 ms 23788 KB Output is correct
22 Incorrect 511 ms 62316 KB Output isn't correct
23 Halted 0 ms 0 KB -