oj.uz

Submission #296868

# Submission time Handle Problem Language Result Execution time Memory
296868 2020-09-11T02:47:29 Z Lawliet Pipes (BOI13_pipes) C++17
41.4815 / 100
 399 ms 29816 KB 
#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( cur );
	}
}

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

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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4992 KB Output isn't correct
2 Incorrect 4 ms 4992 KB Output isn't correct
3 Incorrect 4 ms 5120 KB Output isn't correct
4 Incorrect 116 ms 15992 KB Output isn't correct
5 Incorrect 4 ms 4992 KB Output isn't correct
6 Incorrect 4 ms 4992 KB Output isn't correct
7 Incorrect 4 ms 4992 KB Output isn't correct
8 Incorrect 4 ms 4992 KB Output isn't correct
9 Incorrect 4 ms 5120 KB Output isn't correct
10 Incorrect 4 ms 5120 KB Output isn't correct
11 Incorrect 5 ms 5120 KB Output isn't correct
12 Incorrect 4 ms 5120 KB Output isn't correct
13 Incorrect 90 ms 13688 KB Output isn't correct
14 Incorrect 108 ms 15352 KB Output isn't correct
15 Incorrect 117 ms 15992 KB Output isn't correct
16 Incorrect 95 ms 14332 KB Output isn't correct
17 Incorrect 113 ms 15992 KB Output isn't correct
18 Incorrect 117 ms 15992 KB Output isn't correct
19 Incorrect 116 ms 15480 KB Output isn't correct
20 Incorrect 4 ms 4992 KB Output isn't correct
21 Incorrect 4 ms 5120 KB Output isn't correct
22 Incorrect 115 ms 15996 KB Output isn't correct
23 Incorrect 87 ms 13688 KB Output isn't correct
24 Incorrect 119 ms 15992 KB Output isn't correct
25 Incorrect 93 ms 14200 KB Output isn't correct

Subtask #2
41.4814814815 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 4992 KB Output isn't correct
2 Incorrect 5 ms 5120 KB Output isn't correct
3 Correct 96 ms 14968 KB Output is correct
4 Correct 98 ms 13688 KB Output is correct
5 Correct 94 ms 13560 KB Output is correct
6 Correct 399 ms 27500 KB Output is correct
7 Incorrect 4 ms 4992 KB Output isn't correct
8 Correct 4 ms 4992 KB Output is correct
9 Incorrect 4 ms 4992 KB Output isn't correct
10 Correct 4 ms 4992 KB Output is correct
11 Correct 4 ms 5120 KB Output is correct
12 Correct 4 ms 4992 KB Output is correct
13 Correct 5 ms 5152 KB Output is correct
14 Incorrect 4 ms 4992 KB Output isn't correct
15 Incorrect 4 ms 5120 KB Output isn't correct
16 Incorrect 4 ms 5120 KB Output isn't correct
17 Correct 4 ms 5120 KB Output is correct
18 Correct 4 ms 5120 KB Output is correct
19 Correct 4 ms 5120 KB Output is correct
20 Correct 4 ms 5120 KB Output is correct
21 Correct 5 ms 5120 KB Output is correct
22 Incorrect 4 ms 5120 KB Output isn't correct
23 Incorrect 82 ms 13688 KB Output isn't correct
24 Incorrect 113 ms 15960 KB Output isn't correct
25 Correct 95 ms 14968 KB Output is correct
26 Correct 97 ms 13688 KB Output is correct
27 Correct 95 ms 13560 KB Output is correct
28 Correct 100 ms 13816 KB Output is correct
29 Correct 361 ms 24108 KB Output is correct
30 Incorrect 96 ms 15096 KB Output isn't correct
31 Incorrect 113 ms 15608 KB Output isn't correct
32 Runtime error 113 ms 29816 KB Execution killed with signal 11
33 Correct 107 ms 15736 KB Output is correct
34 Correct 97 ms 13688 KB Output is correct
35 Correct 96 ms 13688 KB Output is correct
36 Correct 99 ms 13816 KB Output is correct
37 Correct 397 ms 27640 KB Output is correct
38 Incorrect 111 ms 15608 KB Output isn't correct
39 Incorrect 100 ms 15608 KB Output isn't correct
40 Incorrect 111 ms 15736 KB Output isn't correct
41 Runtime error 108 ms 29352 KB Execution killed with signal 11
42 Correct 97 ms 13688 KB Output is correct
43 Correct 129 ms 13676 KB Output is correct
44 Correct 100 ms 13560 KB Output is correct
45 Correct 283 ms 23544 KB Output is correct
46 Incorrect 97 ms 15292 KB Output isn't correct
47 Incorrect 125 ms 16116 KB Output isn't correct
48 Incorrect 113 ms 15776 KB Output isn't correct
49 Incorrect 115 ms 15396 KB Output isn't correct
50 Correct 100 ms 13728 KB Output is correct
51 Correct 94 ms 13804 KB Output is correct
52 Correct 98 ms 13560 KB Output is correct
53 Correct 329 ms 24144 KB Output is correct
54 Incorrect 114 ms 15736 KB Output isn't correct