제출 #255646

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
255646		Saboon	Pipes (BOI13_pipes)	C++14	74.07 / 100	111 ms	27764 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 DFS(int v, int idx = -1){
	for (auto [u,i] : g[v]){
		if (i == idx or h[u] != -1)
			continue;
		h[u] = h[v] + 1;
		DFS(u,i);
		x[v] -= w[i] / 2;
	}
	if (!mark[v] and idx != -1){
		w[idx] = 2 * x[v];
		x[v] = 0;
	}
	assert(x[v] == 0);
}

void dfs(int v){
	up[v] = h[v];
	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;
	if (!cyc.empty())
		root = cyc[0];
	DFS(root);
	for (int i = 0; i < m; i++)
		cout << w[i] << '\n';
}

컴파일 시 표준 에러 (stderr) 메시지

pipes.cpp: In function 'void DFS(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 dfs(int)':
pipes.cpp:33:12: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
  for (auto [u,i] : g[v]){
            ^
pipes.cpp:33:16: warning: unused variable 'i' [-Wunused-variable]
  for (auto [u,i] : g[v]){
                ^

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