oj.uz

Submission #334706

# Submission time Handle Problem Language Result Execution time Memory
334706 2020-12-09T20:43:05 Z Lawliet Designated Cities (JOI19_designated_cities) C++17
100 / 100
 734 ms 66240 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;

const int MAXN = 200010;

int n, q;

int degree[MAXN];

lli sumDown;

lli ans[MAXN];
lli curPath[MAXN];
lli depthUp[MAXN];
lli depthDown[MAXN];

bool mark[MAXN];

vector<int> adj[MAXN];
vector<int> weight[MAXN];
vector<int> weightInv[MAXN];

vector<lli> allPaths;

set< pair<lli,int> > s;

void DFSCalculate(int cur, int p)
{
	for(int i = 0 ; i < (int)adj[cur].size() ; i++)
	{
		int viz = adj[cur][i];
		int w = weight[cur][i];

		if( viz == p )
		{
			depthUp[cur] = depthUp[viz] + w;
			break;
		}
	}

	for(int i = 0 ; i < (int)adj[cur].size() ; i++)
	{
		int viz = adj[cur][i];
		int w = weight[cur][i];

		if( viz == p ) continue;
		
		sumDown += w;
		depthDown[viz] = depthDown[cur] + w;

		DFSCalculate( viz , cur );
	}
}

int getIndAnc(int node)
{
	for(int i = 0 ; i < (int)adj[node].size() ; i++)
		if( !mark[ adj[node][i] ] ) return i;
}

void add(int node)
{
	mark[node] = true;

	int indAnc = getIndAnc(node);
	curPath[node] += weightInv[node][indAnc];

	s.insert( { curPath[node] , node } );
}

void topologicalSorting()
{
	for(int i = 1 ; i <= n ; i++)
		if( degree[i] == 1 ) add( i );

	while( (int)s.size() > 2 )
	{
		int node = s.begin()->second;
		s.erase( s.begin() );

		int anc = adj[node][ getIndAnc(node) ];
		degree[anc]--;

		if( degree[anc] == 1 ) 
		{
			curPath[anc] = curPath[node];
			add( anc );
		}
		else allPaths.push_back( curPath[node] );
	}
}

int main()
{
	scanf("%d",&n);

	for(int i = 1 ; i < n ; i++)
	{
		int U, V, W1, W2;
		scanf("%d %d %d %d",&U,&V,&W1,&W2);

		adj[U].push_back( V );
		adj[V].push_back( U );

		weight[U].push_back( W1 );
		weight[V].push_back( W2 );

		weightInv[U].push_back( W2 );
		weightInv[V].push_back( W1 );

		degree[U]++; degree[V]++;
	}

	DFSCalculate( 1 , 1 );

	ans[1] = sumDown;

	for(int i = 1 ; i <= n ; i++)
		ans[1] = min( ans[1] , sumDown + depthUp[i] - depthDown[i] );

	topologicalSorting();

	for(int i = 1 ; i < (int)allPaths.size() ; i++)
		allPaths[i] += allPaths[i - 1];

	scanf("%d",&q);

	for(int i = 1 ; i <= q ; i++)
	{
		int qtd;
		scanf("%d",&qtd);

		if( qtd == 1 )
		{
			printf("%lld\n",ans[1]);
			continue;
		}

		int ind = (int)allPaths.size() - 1 - qtd + 2;

		if( ind < 0 )
		{
			printf("0\n");
			continue;
		}

		printf("%lld\n",allPaths[ind]);
	}
}

Compilation message

designated_cities.cpp: In function 'int getIndAnc(int)':
designated_cities.cpp:61:1: warning: control reaches end of non-void function [-Wreturn-type]
   61 | }
      | ^
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   97 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
designated_cities.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  102 |   scanf("%d %d %d %d",&U,&V,&W1,&W2);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:128:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  128 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
designated_cities.cpp:133:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  133 |   scanf("%d",&qtd);
      |   ~~~~~^~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14444 KB Output is correct
2 Correct 10 ms 14444 KB Output is correct
3 Correct 10 ms 14444 KB Output is correct
4 Correct 10 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 10 ms 14444 KB Output is correct
7 Correct 10 ms 14444 KB Output is correct
8 Correct 10 ms 14444 KB Output is correct
9 Correct 10 ms 14444 KB Output is correct
10 Correct 10 ms 14444 KB Output is correct
11 Correct 10 ms 14444 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 674 ms 45804 KB Output is correct
3 Correct 485 ms 50156 KB Output is correct
4 Correct 629 ms 45672 KB Output is correct
5 Correct 665 ms 46684 KB Output is correct
6 Correct 650 ms 47340 KB Output is correct
7 Correct 623 ms 49624 KB Output is correct
8 Correct 492 ms 52972 KB Output is correct
9 Correct 547 ms 56260 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14444 KB Output is correct
2 Correct 673 ms 45672 KB Output is correct
3 Correct 484 ms 52204 KB Output is correct
4 Correct 623 ms 45676 KB Output is correct
5 Correct 666 ms 46556 KB Output is correct
6 Correct 660 ms 47592 KB Output is correct
7 Correct 561 ms 55000 KB Output is correct
8 Correct 558 ms 51432 KB Output is correct
9 Correct 535 ms 56292 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14444 KB Output is correct
2 Correct 10 ms 14444 KB Output is correct
3 Correct 10 ms 14444 KB Output is correct
4 Correct 10 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 10 ms 14444 KB Output is correct
7 Correct 10 ms 14444 KB Output is correct
8 Correct 10 ms 14444 KB Output is correct
9 Correct 10 ms 14444 KB Output is correct
10 Correct 10 ms 14444 KB Output is correct
11 Correct 10 ms 14444 KB Output is correct
12 Correct 10 ms 14444 KB Output is correct
13 Correct 13 ms 14828 KB Output is correct
14 Correct 12 ms 14828 KB Output is correct
15 Correct 13 ms 14828 KB Output is correct
16 Correct 13 ms 14828 KB Output is correct
17 Correct 13 ms 14956 KB Output is correct
18 Correct 13 ms 14828 KB Output is correct
19 Correct 13 ms 14828 KB Output is correct
20 Correct 13 ms 14828 KB Output is correct
21 Correct 13 ms 14828 KB Output is correct
22 Correct 13 ms 14828 KB Output is correct
23 Correct 13 ms 14828 KB Output is correct
24 Correct 13 ms 14956 KB Output is correct
25 Correct 12 ms 14956 KB Output is correct
26 Correct 13 ms 14956 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 674 ms 45804 KB Output is correct
3 Correct 485 ms 50156 KB Output is correct
4 Correct 629 ms 45672 KB Output is correct
5 Correct 665 ms 46684 KB Output is correct
6 Correct 650 ms 47340 KB Output is correct
7 Correct 623 ms 49624 KB Output is correct
8 Correct 492 ms 52972 KB Output is correct
9 Correct 547 ms 56260 KB Output is correct
10 Correct 10 ms 14444 KB Output is correct
11 Correct 673 ms 45672 KB Output is correct
12 Correct 484 ms 52204 KB Output is correct
13 Correct 623 ms 45676 KB Output is correct
14 Correct 666 ms 46556 KB Output is correct
15 Correct 660 ms 47592 KB Output is correct
16 Correct 561 ms 55000 KB Output is correct
17 Correct 558 ms 51432 KB Output is correct
18 Correct 535 ms 56292 KB Output is correct
19 Correct 10 ms 14444 KB Output is correct
20 Correct 690 ms 45936 KB Output is correct
21 Correct 483 ms 58604 KB Output is correct
22 Correct 630 ms 50540 KB Output is correct
23 Correct 696 ms 51820 KB Output is correct
24 Correct 672 ms 50920 KB Output is correct
25 Correct 673 ms 51940 KB Output is correct
26 Correct 665 ms 50920 KB Output is correct
27 Correct 686 ms 52836 KB Output is correct
28 Correct 664 ms 53484 KB Output is correct
29 Correct 658 ms 51560 KB Output is correct
30 Correct 646 ms 52700 KB Output is correct
31 Correct 611 ms 57936 KB Output is correct
32 Correct 549 ms 57840 KB Output is correct
33 Correct 544 ms 62672 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14444 KB Output is correct
2 Correct 10 ms 14444 KB Output is correct
3 Correct 10 ms 14444 KB Output is correct
4 Correct 10 ms 14444 KB Output is correct
5 Correct 10 ms 14444 KB Output is correct
6 Correct 10 ms 14444 KB Output is correct
7 Correct 10 ms 14444 KB Output is correct
8 Correct 10 ms 14444 KB Output is correct
9 Correct 10 ms 14444 KB Output is correct
10 Correct 10 ms 14444 KB Output is correct
11 Correct 10 ms 14444 KB Output is correct
12 Correct 10 ms 14464 KB Output is correct
13 Correct 674 ms 45804 KB Output is correct
14 Correct 485 ms 50156 KB Output is correct
15 Correct 629 ms 45672 KB Output is correct
16 Correct 665 ms 46684 KB Output is correct
17 Correct 650 ms 47340 KB Output is correct
18 Correct 623 ms 49624 KB Output is correct
19 Correct 492 ms 52972 KB Output is correct
20 Correct 547 ms 56260 KB Output is correct
21 Correct 10 ms 14444 KB Output is correct
22 Correct 673 ms 45672 KB Output is correct
23 Correct 484 ms 52204 KB Output is correct
24 Correct 623 ms 45676 KB Output is correct
25 Correct 666 ms 46556 KB Output is correct
26 Correct 660 ms 47592 KB Output is correct
27 Correct 561 ms 55000 KB Output is correct
28 Correct 558 ms 51432 KB Output is correct
29 Correct 535 ms 56292 KB Output is correct
30 Correct 10 ms 14444 KB Output is correct
31 Correct 13 ms 14828 KB Output is correct
32 Correct 12 ms 14828 KB Output is correct
33 Correct 13 ms 14828 KB Output is correct
34 Correct 13 ms 14828 KB Output is correct
35 Correct 13 ms 14956 KB Output is correct
36 Correct 13 ms 14828 KB Output is correct
37 Correct 13 ms 14828 KB Output is correct
38 Correct 13 ms 14828 KB Output is correct
39 Correct 13 ms 14828 KB Output is correct
40 Correct 13 ms 14828 KB Output is correct
41 Correct 13 ms 14828 KB Output is correct
42 Correct 13 ms 14956 KB Output is correct
43 Correct 12 ms 14956 KB Output is correct
44 Correct 13 ms 14956 KB Output is correct
45 Correct 10 ms 14444 KB Output is correct
46 Correct 690 ms 45936 KB Output is correct
47 Correct 483 ms 58604 KB Output is correct
48 Correct 630 ms 50540 KB Output is correct
49 Correct 696 ms 51820 KB Output is correct
50 Correct 672 ms 50920 KB Output is correct
51 Correct 673 ms 51940 KB Output is correct
52 Correct 665 ms 50920 KB Output is correct
53 Correct 686 ms 52836 KB Output is correct
54 Correct 664 ms 53484 KB Output is correct
55 Correct 658 ms 51560 KB Output is correct
56 Correct 646 ms 52700 KB Output is correct
57 Correct 611 ms 57936 KB Output is correct
58 Correct 549 ms 57840 KB Output is correct
59 Correct 544 ms 62672 KB Output is correct
60 Correct 9 ms 14444 KB Output is correct
61 Correct 715 ms 54340 KB Output is correct
62 Correct 512 ms 58092 KB Output is correct
63 Correct 666 ms 52708 KB Output is correct
64 Correct 734 ms 54116 KB Output is correct
65 Correct 704 ms 52840 KB Output is correct
66 Correct 716 ms 54268 KB Output is correct
67 Correct 702 ms 53016 KB Output is correct
68 Correct 706 ms 55200 KB Output is correct
69 Correct 690 ms 55820 KB Output is correct
70 Correct 674 ms 53092 KB Output is correct
71 Correct 672 ms 55512 KB Output is correct
72 Correct 660 ms 59512 KB Output is correct
73 Correct 592 ms 58980 KB Output is correct
74 Correct 592 ms 66240 KB Output is correct