Submission #1256147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256147		jerzyk	Graph (BOI20_graph)	C++20	100 / 100	130 ms	34588 KiB

Graph

#include <bits/stdc++.h>
     
using namespace std;
typedef double d;
const int N = 100 * 1000 + 7;
const int I = 1000 * 1000 * 1000;
d w[2][N], kon[N];
vector<int> gd;
vector<d> l, od;
vector<pair<int, int>> kraw[N];

void DFS(int v, int r, d &x)
{
	int i;
	if(w[r * -1 + 1][v] != I && x != -I)
	{
    	if(x != I && x != (w[0][v] - w[1][v]) / 2)
    		x = -I;
    	else
			x = min((w[0][v] - w[1][v]) / 2, x);
    }
	//cout << v << " " << r << " " << w[r][v] << " " << x << "\n";
    gd.push_back(v);
    if(r == 0)
    {
    	od.push_back(w[r][v] * -1);
    	l.push_back(w[r][v]);
	}else
    {
		l.push_back(w[r][v] * -1);
    	od.push_back(w[r][v]);
	}
    //l.push_back(w[r][v]);
    //l.push_back(w[r][v] * -1);
   	for(i = 0; i < (int)kraw[v].size(); ++i)
    {
		if(i != 0 && kraw[v][i].first == kraw[v][i - 1].first && kraw[v][i].second != kraw[v][i - 1].second)
    		x = -I;
    	if(w[r * -1 + 1][kraw[v][i].first] != I && w[r * -1 + 1][kraw[v][i].first] !=  (d)kraw[v][i].second - w[r][v])
			x = -I;
    	if(w[r * -1 + 1][kraw[v][i].first] != I)
    		continue;
    	w[r * -1 + 1][kraw[v][i].first] = (d)kraw[v][i].second - w[r][v];
    	DFS(kraw[v][i].first, r * -1 + 1, x); 
    }
}

d Licz(d x)
{
    int i;
    d wynik;
    wynik = 0;
    for(i = 0; i < (int)od.size(); ++i)
    {
    	wynik += abs(od[i] + x);
    }
    return wynik;
}
     
d Ternary()
{
	//int i;
	sort(l.begin(), l.end());
	//for(i = 0; i < (int)l.size(); ++i)
		//cout << i << " " << l[i] << "\n";
    return l[(int)l.size() / 2];
}
     
void Wynik(int &n)
{
    int i, j;
    d x;
    for(i = 1; i <= n; ++i)
    {
		l.clear();
		gd.clear();
		od.clear();
    	if(w[0][i] != I || w[1][i] != I)
    		continue;
    	x = I;
    	w[1][i] = 0;
    	DFS(i, 1, x);
    	if(x == (d)(-I))
    	{
    		cout << "NO\n";
    		return;
    	}
    	if(x == I)
			x = Ternary();
		//cout << i << " " << x << "\n";
    	for(j = 0; j < (int)gd.size(); ++j)
    	{
    		if(w[0][gd[j]] != I)
    			kon[gd[j]] = w[0][gd[j]] - x;
    		else
    			kon[gd[j]] = w[1][gd[j]] + x;
    	}
    }
    cout << "YES\n";
    for(i = 1; i <= n; ++i)
    	cout << kon[i] << " ";
    cout << "\n";
}
     
void WczytajLiczby(int &n)
{
    int m, a, b, c, i;
    cin >> n >> m;
    for(i = 1; i <= m; ++i)
    {
    	cin >> a >> b >> c;
    	kraw[a].push_back(make_pair(b, c));
    	kraw[b].push_back(make_pair(a, c));
    }
    for(i = 1; i <= n; ++i)
    {
    	sort(kraw[i].begin(), kraw[i].end());
    	w[0][i] = I;
    	w[1][i] = I;
    }
}
     
void Gra()
{
   	int n;
   	WczytajLiczby(n);
   	Wynik(n);
}
     
int main ()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    Gra();
    
    return 0;
}

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