Submission #334706

#	Time	Username	Problem	Language	Result	Execution time	Memory
334706		Lawliet	Designated Cities (JOI19_designated_cities)	C++17	100 / 100	734 ms	66240 KiB

designated_cities

#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 (stderr)

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 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 17 / 17
• Subtask 6: 44 / 44