Submission #255662

#	Time	Username	Problem	Language	Result	Execution time	Memory
255662		Saboon	Pipes (BOI13_pipes)	C++14	100 / 100	138 ms	14576 KiB

pipes

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int maxn = 1e5 + 10;

vector<pair<int,int>> g[maxn];
int h[maxn], up[maxn];
ll x[maxn], w[maxn];

vector<int> cyc;
bool mark[maxn];

void dfs3(int v, int idx = -1){
	for (auto [u,i] : g[v]){
		if (i == idx or !mark[u] or h[u] != -1)
			continue;
		h[u] = h[v] + 1;
		dfs3(u,i);
		x[v] -= w[i]/2;
	}
	if (idx != -1){
		w[idx] = 2ll * x[v];
		x[v] = 0;
	}
}

void dfs2(int v, int idx = -1){
	for (auto [u,i] : g[v]){
		if (i == idx or h[u] != -1)
			continue;
		h[u] = h[v] + 1;
		dfs2(u,i);
		x[v] -= w[i] / 2;
	}
	if (!mark[v] and idx != -1){
		w[idx] = 2ll * x[v];
		x[v] = 0;
	}
}

void dfs(int v){
	up[v] = maxn;
	for (auto [u,i] : g[v]){
		if (h[u] == -1){
			h[u] = h[v] + 1;
			dfs(u);
			up[v] = min(up[v], up[u]);
		}
		else if (h[u] != h[v]-1){
			if (h[u] % 2 != h[v] % 2){
				cout << 0 << endl;
				exit(0);
			}
			up[v] = min(up[v], h[u]);
		}
	}
	if (up[v] <= h[v]){
		mark[v] = 1;
		cyc.push_back(v);
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	if (m > n){
		cout << 0 << endl;
		exit(0);
	}
	for (int i = 1; i <= n; i++)
		cin >> x[i];
	for (int i = 0; i < m; i++){
		int v, u;
		cin >> v >> u;
		g[v].push_back({u,i});
		g[u].push_back({v,i});
	}
	memset(h, -1, sizeof h);
	h[1] = 0;
	dfs(1);
	memset(h, -1, sizeof h);
	int root = 1;
	reverse(cyc.begin(), cyc.end());
	if (!cyc.empty())
		root = cyc[0];
	h[root] = 0;
	dfs2(root);
	if (!cyc.empty()){
		int v = cyc[0], u = cyc.back();
		int idx = -1;
		for (auto [w,i] : g[v])
			if (u == w)
				idx = i;
		ll sign = 1;
		for (int i = 0; i < cyc.size(); i++){
			w[idx] += sign*2*x[cyc[i]];
			sign *= -1;	
		}
		w[idx] /= 2;
		x[v] -= w[idx]/2;
		x[u] -= w[idx]/2;
		memset(h, -1, sizeof h);
		h[root] = 0;
		dfs3(root);
	}
	for (int i = 0; i < m; i++)
		cout << w[i] << '\n';
}

Compilation message (stderr)

pipes.cpp: In function 'void dfs3(int, int)':
pipes.cpp:17:12: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
  for (auto [u,i] : g[v]){
            ^
pipes.cpp: In function 'void dfs2(int, int)':
pipes.cpp:31:12: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
  for (auto [u,i] : g[v]){
            ^
pipes.cpp: In function 'void dfs(int)':
pipes.cpp:46:12: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
  for (auto [u,i] : g[v]){
            ^
pipes.cpp:46:16: warning: unused variable 'i' [-Wunused-variable]
  for (auto [u,i] : g[v]){
                ^
pipes.cpp: In function 'int main()':
pipes.cpp:95:13: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
   for (auto [w,i] : g[v])
             ^
pipes.cpp:99:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < cyc.size(); i++){
                   ~~^~~~~~~~~~~~

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