Submission #1256237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256237		jerzyk	Graph (BOI20_graph)	C++20	100 / 100	90 ms	18496 KiB

Graph

#include <bits/stdc++.h>
     
using namespace std;
const int N = 100 * 1000 + 7;
const int I = 1000 * 1000 * 1000;
vector<pair<int, int>> ed[N];
pair<int, int> val[N];
vector<int> cur;
long double answer[N];

void DFS(int v)
{
    cur.push_back(v);
	for(int i = 0; i < (int)ed[v].size(); ++i)
    {
        if(val[ed[v][i].first].first != 0) continue;
        val[ed[v][i].first].first = -val[v].first;
        val[ed[v][i].first].second = ed[v][i].second - val[v].second;
        DFS(ed[v][i].first);
    }
}

bool Do()
{
    bool czy = 1;
    vector<int> pos;
    long double x = -I - 10;
    int ts = -I * 2;
    for(int i = 0; i < (int)cur.size(); ++i)
    {
        int v = cur[i];
        pos.push_back(val[v].first * val[v].second * -1);
        for(int j = 0; j < (int)ed[v].size(); ++j)
        {
            int ne = ed[v][j].first;
            if(val[v].first == val[ne].first)
            {
                if(ts > -I * 2 && ts != (ed[v][j].second - val[v].second - val[ne].second) * val[v].first)
                    czy = 0;
                ts = (ed[v][j].second - val[v].second - val[ne].second) * val[v].first;
            }
            else if(val[v].second + val[ne].second != ed[v][j].second)
                czy = 0;
        }
    }
    sort(pos.begin(), pos.end());
    if(ts == -I * 2)
        x = pos[(int)pos.size() / 2];
    else
        x = (long double)ts / (long double)2;
    for(int i = 0; i < (int)cur.size(); ++i)
    {
        int v = cur[i];
        answer[v] = x * (long double)val[v].first + (long double)val[v].second;
    }
    cur.clear();
    return czy;
}
     
void Wynik(int &n)
{
    bool czy = 1;
    for(int i = 1; i <= n; ++i)
    {
		if(val[i].first != 0) continue;
        val[i].first = 1;
        DFS(i);
        czy = (czy & Do());
    }
    if(czy == 0)
    {
        cout << "NO\n";
        return;
    }
    cout << "YES\n";
    cout << fixed << setprecision(1);
    for(int i = 1; i <= n; ++i)
    	cout << answer[i] << " ";
    cout << "\n";
}
     
void WczytajLiczby(int &n)
{
    int m, a, b, c;
    cin >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
    	cin >> a >> b >> c;
    	ed[a].push_back(make_pair(b, c));
    	ed[b].push_back(make_pair(a, c));
    }
}
     
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