Submission #110771

#	Time	Username	Problem	Language	Result	Execution time	Memory
110771		ckodser	Pipes (BOI13_pipes)	C++14	74.07 / 100	175 ms	14580 KiB

pipes

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int N = 100005;
int n, m, cv, cu, A[N], B[N], M[N], P[N], R[N];
ll C[N], D[N];
vector < int > Adj[N];
void DFSC(int v, int p)
{
	M[v] = 1;
	for (int id : Adj[v])
		if (id != p)
		{
			int u = A[id] ^ B[id] ^ v;
			if (M[u])
				cv = v, cu = u;
			if (!M[u])
				P[u] = v, DFSC(u, id);
		}
}
void DFS(int v, int p)
{
	for (int id : Adj[v])
		if (id != p)
			DFS(A[id] ^ B[id] ^ v, id);
	int par = A[p] ^ B[p] ^ v;
	D[p] += C[v] + C[v];
	C[par] -= C[v];
	C[v] = 0;
}
void DFS2(int v, int p)
{
	M[v] = 2;
	P[v] = p;
	R[v] = Adj[v][0] ^ Adj[v][1] ^ p;
	int u = A[R[v]] ^ B[R[v]] ^ v;
	if (M[u] != 2)
		DFS2(u, R[v]);
}
int main()
{
	scanf("%d%d", &n, &m);
	if (m > n) return !printf("0\n");
	for (int i = 1; i <= n; i++)
		scanf("%lld", &C[i]);
	for (int i = 1; i <= m; i++)
	{
		scanf("%d%d", &A[i], &B[i]);
		Adj[A[i]].pb(i);
		Adj[B[i]].pb(i);
	}
	DFSC(1, 0);
	if (!cv)
		cv = cu = 1;
	vector < int > vec;
	vec.pb(cu);
	while (cv != cu)
		cu = P[cu], vec.pb(cu);
	if ((int)vec.size() % 2 == 0)
		return !printf("0\n");
	memset(M, 0, sizeof(M));
	for (int v : vec)
		M[v] = 1;
	for (int v : vec)
		for (int id : Adj[v])
		{
			int u = A[id] ^ B[id] ^ v;
			if (!M[u]) DFS(u, id);
		}
	if (vec.size() > 1)
	{
		for (int v : vec)
		{
			for (int i = 0; i < (int)Adj[v].size(); i++)
			{
				int id = Adj[v][i];
				if (!M[A[id] ^ B[id] ^ v])
					swap(Adj[v][i], Adj[v].back()), Adj[v].pop_back(), i --;
			}
			assert(Adj[v].size() == 2);
		}
		int idd = Adj[vec[0]][0];
		if ((A[idd] ^ B[idd] ^ vec[0]) != vec[1])
			DFS2(vec[0], Adj[vec[0]][0]);
		else
			DFS2(vec[0], Adj[vec[0]][1]);
		vector < ll > Df(vec.size(), 0);
		for (int i = 2; i != 0; i = (i + 2) % (int)vec.size())
		{
			int p1 = i - 1;
			int p2 = i - 2;
			if (p1 < 0)
				p1 += (int)vec.size();
			if (p2 < 0)
				p2 += (int)vec.size();
			Df[i] = Df[p2] - C[vec[p2]] + C[vec[p1]];
		}
		ll sum = 0;
		for (int i = 0; i < (int)vec.size(); i++)
			sum += C[vec[i]];
		sum /= 2;
		for (int i = 0; i < (int)vec.size(); i++)
			sum -= Df[i];
		sum /= (int)vec.size();
		for (int i = 0; i < (int)vec.size(); i++)
			D[P[vec[i]]] += sum + Df[i];
	}
	for (int i = 1; i <= m; i++)
		printf("%lld\n", D[i]);
	return 0;
}

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
pipes.cpp:46:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &C[i]);
   ~~~~~^~~~~~~~~~~~~~~
pipes.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &A[i], &B[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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