Submission #297244

#	Time	Username	Problem	Language	Result	Execution time	Memory
297244		Lawliet	Pipes (BOI13_pipes)	C++17	100 / 100	402 ms	27640 KiB

pipes

#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;

const int MAXN = 100010;
const int MAXM = 500010;

int n, m;

int v[MAXN];
int degree[MAXN];

lli ans[MAXM];
lli curSum[MAXN];

bool mark[MAXN];

vector<int> adj[MAXN];
vector<int> indEdge[MAXN];

queue<int> q;

void add(int cur)
{
	q.push(cur);
	mark[cur] = true;
}

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

	return -1;
}

lli getDiff(int cur) { return v[cur] - curSum[cur]; }

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

	while( !q.empty() )
	{
		int cur = q.front();
		q.pop();

		int nxtInd = nextIndEdge( cur );

		int anc = adj[cur][nxtInd];
		int ind = indEdge[cur][nxtInd];

		ans[ind] = getDiff(cur);
		curSum[cur] += ans[ind]; curSum[anc] += ans[ind];

		if( --degree[anc] == 1 )
			add( anc );
	}
}

void addEdge(int U, int V, int i)
{
	adj[U].push_back( V );
	adj[V].push_back( U );

	indEdge[U].push_back( i );
	indEdge[V].push_back( i );

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

void notUnique()
{
	printf("0\n");
	exit(0);
}

void printAnswer()
{
	for(int i = 1 ; i <= m ; i++)
		printf("%lld\n",2*ans[i]);
}

void findAnswerCycle()
{
	int rootCycle;

	for(int i = 1 ; i <= n ; i++)
		if( !mark[i] ) rootCycle = i;

	int cur = rootCycle;

	vector<int> cycleNodes;
	vector<int> cycleEdges;

	while( !mark[cur] )
	{
		mark[cur] = true;
		cycleNodes.push_back( cur );

		int nxtInd = nextIndEdge( cur );

		if( nxtInd == -1 ) break;
		
		cycleEdges.push_back( indEdge[cur][nxtInd] );
		cur = adj[cur][nxtInd];
	}

	for(int i = 0 ; i < (int)adj[cur].size() ; i++)
		if( adj[cur][i] == rootCycle ) cycleEdges.push_back( indEdge[cur][i] );

	lli sumCycle = 0;
	int szCycle = (int)cycleNodes.size();

	if( szCycle%2 == 0 ) notUnique();

	for(int i = 0 ; i < szCycle ; i++)
		sumCycle += getDiff( cycleNodes[i] );

	sumCycle /= 2;

	lli sumPrefix[] = { 0 , 0 };
	lli sumSuffix[] = { 0 , 0 };

	for(int i = 0 ; i < szCycle ; i++)
		sumSuffix[i%2] += getDiff( cycleNodes[i] );

	for(int i = 0 ; i < szCycle ; i++)
	{
		sumPrefix[i%2] += getDiff( cycleNodes[i] );
		sumSuffix[i%2] -= getDiff( cycleNodes[i] );

		ans[ cycleEdges[i] ] = sumCycle - sumPrefix[1 - i%2] - sumSuffix[i%2];
	}
}

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

	for(int i = 1 ; i <= n ; i++)
		scanf("%d",&v[i]);

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

		addEdge( U , V , i );
	}

	if( m > n ) notUnique();

	if( m == n - 1 ) addEdge( 1 , 1 , n );
	
	topologicalSorting();

	if( m == n ) findAnswerCycle();
	printAnswer();
}

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:141:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  141 |  scanf("%d %d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~
pipes.cpp:144:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  144 |   scanf("%d",&v[i]);
      |   ~~~~~^~~~~~~~~~~~
pipes.cpp:149:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  149 |   scanf("%d %d",&U,&V);
      |   ~~~~~^~~~~~~~~~~~~~~
pipes.cpp: In function 'void findAnswerCycle()':
pipes.cpp:98:18: warning: 'rootCycle' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |  while( !mark[cur] )
      |          ~~~~~~~~^

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70