Submission #1126178

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126178		KasymK	Pipes (BOI13_pipes)	C++20	79.26 / 100	343 ms	52872 KiB

pipes

#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define tr(i, c) for(auto i = c.begin(); i != c.end(); ++i)
#define wr puts("----------------")
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int N = 1e5+5;
set<pii> adj[N];
ll c[N], ans[N], p[N];
bool vis[N];;

int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i)
		scanf("%lld", c+i);
	for(int i = 1; i <= m; ++i){
		int a, b;
		scanf("%d%d", &a, &b);
		adj[a].insert({b, i});
		adj[b].insert({a, i});
	}
	if(m>n){
		puts("0");
		return 0;
	}
	queue<int> q;
	for(int i = 1; i <= n; ++i)
		if((int)adj[i].size()<2)
			q.push(i), vis[i]=1;
	int cnt = 0;
	while(!q.empty()){
		int x = q.front();
		q.pop();
		pii P = *adj[x].begin();
		cnt++;
		ans[P.ss] += c[x];
		c[P.ff] -= c[x];
		adj[P.ff].erase({x, P.ss});
		if((int)adj[P.ff].size()<2 and !vis[P.ff])
			q.push(P.ff), vis[P.ff]=1;
	}
	/*
	m>n => infinity
	m=n-1 => cnt=n => always answer
	m=n => we will remove all trees under all nodes, (n-cnt)%2==0 => there is even length cycle => infinity,else one answer.
	*/
	if(cnt<n){
		if((n-cnt)%2==0){
			puts("0");
			return 0; // We found even length cycle
		}
		int ad = -1;
		for(int i = 1; i <= n; ++i)
			if(!vis[i])
				ad = i;
		int x = ad;
		vector<int> a, b;
		while(x!=ad or a.empty()){
			pii P;
			if(a.empty() or adj[x].begin()->ff!=a.back())
				P = *adj[x].begin();
			else
				P = *--adj[x].end();
			a.pb(x);
			b.pb(P.ss);
			x = P.ff;
		}
		int sz = (int)a.size();
		ll mal = 0;
		p[sz-1] = c[a[sz-1]];
		for(int i = n-2; i >= 0; --i)
			p[i] = c[a[i]]-p[i+1];
		for(int i = 0; i < n; ++i){
			mal = c[a[i]]-mal;
			if(i<n-1)
				ans[b[i]] = (mal+p[i+1])/2;
			else
				ans[b[i]] = mal/2;
		}
	}
	// cnt!=n => m=n-1 => normal tree
	for(int i = 1; i <= m; ++i)
		printf("%lld\n", ans[i]*2);
	return 0;
}

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         scanf("%d%d", &n, &m);
      |         ~~~~~^~~~~~~~~~~~~~~~
pipes.cpp:24:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |                 scanf("%lld", c+i);
      |                 ~~~~~^~~~~~~~~~~~~
pipes.cpp:27:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |                 scanf("%d%d", &a, &b);
      |                 ~~~~~^~~~~~~~~~~~~~~~

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