Submission #443988

#	Time	Username	Problem	Language	Result	Execution time	Memory
443988		aryan12	Pipes (BOI13_pipes)	C++17	74.07 / 100	218 ms	29336 KiB

pipes

#include <bits/stdc++.h>
using namespace std;
#define int long long

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e5 + 5;
int change[N], result[N];
vector<pair<int, int> > g[N];
int edgeChange[N], temp[N];
bool vis[N];
int n, m, bruh;
vector<int> cycle, cycle_edges;

void dfs(int node, int par, int edgeNum) {
	for(int i = 0; i < g[node].size(); i++) {
		if(g[node][i].first != par) {
			dfs(g[node][i].first, node, g[node][i].second);
		}
	}
	int netWithParent = change[node] - result[node];
	if(par != -1) {
		result[node] += netWithParent;
		edgeChange[edgeNum] = netWithParent;
		result[par] += netWithParent;
	}
}

void Tree() {
	dfs(1, -1, -1);
	if(result[1] != change[1]) {
		cout << "0\n";
		return;
	}
	for(int i = 1; i <= m; i++) {
		cout << edgeChange[i] * 2 << "\n";
	}
}

void dfs1(int node, int par) {
	vis[node] = true;
	cycle.push_back(node);
	for(int i = 0; i < g[node].size(); i++) {
		if(g[node][i].first == par) {
			continue;
		}
		if(!vis[g[node][i].first]) {
			cycle_edges.push_back(g[node][i].second);
			dfs1(g[node][i].first, node);
		}
		if(g[node][i].first == bruh) {
			cycle_edges.push_back(g[node][i].second);
		}
	}
}

void Solve() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		cin >> change[i];
	}
	for(int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(make_pair(v, i));
		g[v].push_back(make_pair(u, i));
	}
	if(m == n - 1) {
		Tree();
		return;
	}
	if(m > n) {
		cout << "0\n";
		return;
	}
	int cnt = 0;
	queue<int> q;
	for(int i = 1; i <= n; i++) {
		vis[i] = false;
		temp[i] = g[i].size();
		if(temp[i] == 1) {
			q.push(i);
		}
	}
	while(!q.empty()) {
		int node = q.front();
		vis[node] = true;
		q.pop();
		cnt++;
		for(int i = 0; i < g[node].size(); i++) {
			if(!vis[g[node][i].first]) {
				temp[g[node][i].first]--;
				if(temp[g[node][i].first] == 1) {
					q.push(g[node][i].first);
				}
				int netChange = change[node] - result[node];
				edgeChange[g[node][i].second] = netChange;
				result[node] += netChange;
				result[g[node][i].first] += netChange;
			}
		}
	}
	if((n - cnt) % 2 == 0) {
		cout << "0\n";
		return;
	}
	for(int i = 1; i <= n; i++) {
		if(!vis[i]) {
			bruh = i;
			dfs1(i, -1);
		}
	}
	int sum = 0;
	for(int i = 0; i < cycle.size(); i++) {
		if(i % 2 == 0) {
			sum += (change[cycle[i]] - result[cycle[i]]);
		}
		else {
			sum -= (change[cycle[i]] - result[cycle[i]]);
		}
	}
	if(sum % 2 == 1) {
		cout << "0\n";
		return;
	}
	edgeChange[0] = sum / 2;
	for(int i = 1; i < cycle_edges.size(); i++) {
		edgeChange[i] = change[cycle[i - 1]] - result[cycle[i - 1]] - edgeChange[i - 1];
	}
	for(int i = 1; i <= m; i++) {
		cout << edgeChange[i] * 2 << "\n";
	}
}

int32_t main() {
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) {
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

Compilation message (stderr)

pipes.cpp: In function 'void dfs(long long int, long long int, long long int)':
pipes.cpp:16:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for(int i = 0; i < g[node].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
pipes.cpp: In function 'void dfs1(long long int, long long int)':
pipes.cpp:43:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for(int i = 0; i < g[node].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~
pipes.cpp: In function 'void Solve()':
pipes.cpp:90:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |   for(int i = 0; i < g[node].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~
pipes.cpp:114:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |  for(int i = 0; i < cycle.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~
pipes.cpp:127:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |  for(int i = 1; i < cycle_edges.size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~~~~

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