Submission #1169698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169698		behesht	Graph (BOI20_graph)	C++20	100 / 100	97 ms	17684 KiB

Graph

#include <bits/stdc++.h>
 
#define ll          long long
#define pb          push_back
#define mk          make_pair
#define S           second
#define Y           second
#define F           first 
#define X           first
#define debug(x)	cout << #x << " : " << x << endl << flush

using namespace std;

const int INF = 1e9;
const int MAXN = 1e5 + 24;

vector <pair<int, int>> adj[MAXN];
vector <int> Plus, Minus;

int n, m;
double javab[MAXN];
bool vis[MAXN];
double ans;
bool flag = 1;

pair <int, int> p[MAXN]; 

int minb, maxb;
ll ps[MAXN];

bool cmp(int a, int b){
	return (p[a].S < p[b].S);
}

void dfs(int u){
	
	vis[u] = 1;
	
	if(p[u].F == 1)
		Plus.pb(u);
	
	else
		Minus.pb(u);
	
	for(auto x : adj[u]){
		
		int v = x.F;
		int w = x.S;
		w++;
		
		if(vis[v]){
			
			int a = -p[u].F;
			int b = w - p[u].S;
			
			if(a == p[v].F && b != p[v].S)
				flag = 0;
			
			else if(a != p[v].F){
				double esi = (double)(p[v].S - b) / (a - p[v].F);
				
				if(ans == INF)
					ans = esi;
				
				else if(ans != esi)
					flag = 0;
			}
		}
		
		else{
			vis[v] = 1;
			
			p[v].F = -p[u].F;
			p[v].S = w - p[u].S;
			
			dfs(v);
		}
	}
}


signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	
	for(int i=0; i<m; i++){
		int u, v, x;
		cin >> u >> v >> x; // 1 ---> 0 *** 2 ---> 1
		
		u--;
		v--;
		x--;
		
		adj[u].pb(mk(v, x));
		adj[v].pb(mk(u, x));
	}
	
	for(int i=0; i<n; i++){
		
		if(!vis[i]){
			
			ans = INF;
			minb = INF;
			maxb = 0;
			
			p[i].F = 1;
			p[i].S = 0;
			
			Plus.clear();
			Minus.clear();
			
			dfs(i);
			
			if(flag){
				
				if(ans != INF){
					for(auto u : Minus)
						javab[u] = -ans + p[u].S;
					
					for(auto u : Plus)
						javab[u] = ans + p[u].S;
				}
				
				else if(Minus.empty())
					javab[i] = 0;
				
				else{
					
					int mini = INF;
					
					sort(Minus.begin(), Minus.end(), cmp); // -
					sort(Plus.begin(), Plus.end(), cmp); // +
					
					Plus.insert(Plus.begin(), -INF);
					Minus.insert(Minus.begin(), -INF);
					
					int rp = Plus.size(), rm = 1;
					
					for(int k = min(p[Minus[1]].S, -p[Plus.back()].S); k <= max(-p[Plus[1]].S, p[Minus.back()].S); k++){
						
						// Minus
						ps[0] = 0;
						
						for(int j = 1; j < ((int)Minus.size()); j++)
							ps[j] = ps[j - 1] + p[Minus[j]].S - k;
						
						//while(rm < Minus.size() && p[Minus[rm]].S - k < 0)
							//rm++;
						
						int r = Minus.size(), l = 0, mid; // r ---> first Plus
						
						while(r - l > 1){
							mid = (r + l)/2;
							
							if(p[Minus[mid]].S - k >= 0)
								r = mid;
								
							else 
								l = mid;
						}
						
						int sum = ps[((int)Minus.size()) - 1] - ps[r - 1];
						sum -= ps[r - 1];;
						
						
						// Plus
						ps[0] = 0;
						
						for(int j = 1; j < ((int)Plus.size()); j++)
							ps[j] = ps[j - 1] + p[Plus[j]].S + k;
						
						//while(rp > 1 && p[Plus[rp - 1]].S + k >= 0)
							//rp--;
						
						r = Plus.size(), l = 0, mid; // r ---> first Plus
						
						while(r - l > 1){
							mid = (r + l)/2;
							
							if(p[Plus[mid]].S + k >= 0)
								r = mid;
								
							else 
								l = mid;
						}
						
						sum += ps[Plus.size() - 1] - ps[r - 1];
						sum -= ps[r - 1];
						
						if(sum < mini){
							mini = sum;
							ans = k;
						}
					}
					
					for(int j = 1; j < ((int)Minus.size()); j++)
						javab[Minus[j]] = -ans + p[Minus[j]].S;
					
					for(int j = 1; j < ((int)Plus.size()); j++)
						javab[Plus[j]] = ans + p[Plus[j]].S;
				}
			}
			
			else 
				break;
		}
	}
	
	if(flag){
		cout << "YES" << endl;
		
		for(int i=0; i<n; i++)
			cout << javab[i] << " ";
			
		cout << endl;
		exit(0);
	}
	
	cout << "NO" << endl;
}

// Man hamoooonam ke ye roooz...

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 24 / 24
• Subtask 4: 42 / 42
• Subtask 5: 5 / 5