oj.uz

Submission #376160

# Submission time Handle Problem Language Result Execution time Memory
376160 2021-03-11T02:28:40 Z daniel920712 Designated Cities (JOI19_designated_cities) C++14
13 / 100
 689 ms 85996 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];
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);
        }
    }
}
int main()
{
    long long N,M,i,j,k,a,b,c,d,how=1e18;
    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];
            //printf("%lld %lld %lld\n",i,a,b);
            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);
        for(i=1;i<=N;i++)
        {
            how=min(how,ans[i]);
        }
        printf("%lld\n",how);
    }

    return 0;
}

Compilation message

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:49:23: warning: unused variable 'k' [-Wunused-variable]
   49 |     long long N,M,i,j,k,a,b,c,d,how=1e18;
      |                       ^
designated_cities.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |     scanf("%lld",&N);
      |     ~~~~~^~~~~~~~~~~
designated_cities.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |         scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |         scanf("%lld",&M);
      |         ~~~~~^~~~~~~~~~~
designated_cities.cpp:84:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |             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 225 ms 23916 KB Output is correct
3 Correct 181 ms 23788 KB Output is correct
4 Correct 201 ms 23916 KB Output is correct
5 Correct 201 ms 23916 KB Output is correct
6 Correct 199 ms 23788 KB Output is correct
7 Correct 190 ms 23788 KB Output is correct
8 Correct 211 ms 23788 KB Output is correct
9 Correct 198 ms 23868 KB Output is correct
10 Correct 181 ms 23808 KB Output is correct
11 Correct 223 ms 23788 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23788 KB Output is correct
2 Correct 479 ms 62332 KB Output is correct
3 Correct 592 ms 85192 KB Output is correct
4 Correct 459 ms 62188 KB Output is correct
5 Correct 500 ms 62176 KB Output is correct
6 Correct 483 ms 65896 KB Output is correct
7 Correct 561 ms 61660 KB Output is correct
8 Correct 525 ms 85996 KB Output is correct
9 Correct 689 ms 61396 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 225 ms 23916 KB Output is correct
3 Correct 181 ms 23788 KB Output is correct
4 Correct 201 ms 23916 KB Output is correct
5 Correct 201 ms 23916 KB Output is correct
6 Correct 199 ms 23788 KB Output is correct
7 Correct 190 ms 23788 KB Output is correct
8 Correct 211 ms 23788 KB Output is correct
9 Correct 198 ms 23868 KB Output is correct
10 Correct 181 ms 23808 KB Output is correct
11 Correct 223 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 18 ms 23788 KB Output is correct
2 Correct 479 ms 62332 KB Output is correct
3 Correct 592 ms 85192 KB Output is correct
4 Correct 459 ms 62188 KB Output is correct
5 Correct 500 ms 62176 KB Output is correct
6 Correct 483 ms 65896 KB Output is correct
7 Correct 561 ms 61660 KB Output is correct
8 Correct 525 ms 85996 KB Output is correct
9 Correct 689 ms 61396 KB Output is correct
10 Correct 16 ms 23788 KB Output is correct
11 Incorrect 505 ms 62444 KB Output isn't correct
12 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 225 ms 23916 KB Output is correct
3 Correct 181 ms 23788 KB Output is correct
4 Correct 201 ms 23916 KB Output is correct
5 Correct 201 ms 23916 KB Output is correct
6 Correct 199 ms 23788 KB Output is correct
7 Correct 190 ms 23788 KB Output is correct
8 Correct 211 ms 23788 KB Output is correct
9 Correct 198 ms 23868 KB Output is correct
10 Correct 181 ms 23808 KB Output is correct
11 Correct 223 ms 23788 KB Output is correct
12 Correct 18 ms 23788 KB Output is correct
13 Correct 479 ms 62332 KB Output is correct
14 Correct 592 ms 85192 KB Output is correct
15 Correct 459 ms 62188 KB Output is correct
16 Correct 500 ms 62176 KB Output is correct
17 Correct 483 ms 65896 KB Output is correct
18 Correct 561 ms 61660 KB Output is correct
19 Correct 525 ms 85996 KB Output is correct
20 Correct 689 ms 61396 KB Output is correct
21 Correct 16 ms 23788 KB Output is correct
22 Incorrect 505 ms 62444 KB Output isn't correct
23 Halted 0 ms 0 KB -