Submission #447292

#	Time	Username	Problem	Language	Result	Execution time	Memory
447292		jhnah917	Graph (BOI20_graph)	C++14	100 / 100	207 ms	30956 KiB

Graph

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

using ll = long long;
using ld = long double;
using PLL = pair<ll, ll>;
using PDD = pair<ld, ld>;
inline void DIE(){ cout << "NO"; exit(0); }

int N, M;
vector<PLL> G[101010];
PDD A[101010];
bool C[101010];
vector<double> Fix;
vector<ll> Can, Vis;
double R[101010];

void DFS(int v, int mul, ll add){
    if(!C[v]) A[v] = {mul, add};
    else if(A[v].x == mul && A[v].y == add) return;
    else if(A[v].x == mul && A[v].y != add) DIE();
    else{
        Fix.push_back(1.0 * (A[v].y - add) / (mul - A[v].x));
        return;
    }
    Vis.push_back(v); C[v] = true;
    if(mul == 1) Can.push_back(-add);
    else Can.push_back(add);
    for(auto [i,w] : G[v]) DFS(i, -mul, w-add);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    for(int i=1; i<=M; i++){
        int s, e, x; cin >> s >> e >> x;
        G[s].emplace_back(e, x);
        G[e].emplace_back(s, x);
    }
    for(int i=1; i<=N; i++){
        if(C[i]) continue;
        Fix.clear(); Can.clear(); Vis.clear();
        DFS(i, 1, 0);
        sort(Can.begin(), Can.end());
        sort(Fix.begin(), Fix.end());
        Fix.erase(unique(Fix.begin(), Fix.end()), Fix.end());
        if(Fix.size() > 1) DIE();
        double X = Fix.size() == 1 ? Fix[0] : Can[Can.size()/2];
        for(auto j : Vis) R[j] = A[j].x * X + A[j].y;
    }
    cout << "YES\n";
    for(int i=1; i<=N; i++) cout << R[i] << " ";
}

Compilation message (stderr)

Graph.cpp: In function 'void DFS(int, int, ll)':
Graph.cpp:31:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |     for(auto [i,w] : G[v]) DFS(i, -mul, w-add);
      |              ^

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