Submission #447290

#	Time	Username	Problem	Language	Result	Execution time	Memory
447290		jhnah917	Graph (BOI20_graph)	C++14	0 / 100	2 ms	2700 KiB

Graph

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

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

int N, M, S[202020], E[202020], W[202020];
PLL A[101010]; // ax + b
bool C[101010];
vector<PLL> G[101010];
vector<double> X;
vector<ll> V, Y;

double R[101010];

void DFS(int v, ll mul, ll add){
    V.push_back(v);
    A[v] = { mul, add }; C[v] = true;
    if(A[v].x == -1) Y.push_back(A[v].y);
    else Y.push_back(-A[v].y);

    for(auto [i,w] : G[v]){
        PLL nxt(-mul, w - add);
        if(!C[i]) DFS(i, nxt.x, nxt.y);
        else if(A[i] == nxt) continue;
        else if(A[i].x == nxt.x && A[i].y != nxt.y) DIE();
        else X.push_back(1.0 * (A[i].y - nxt.y) / (nxt.x - A[i].x));
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    for(int i=1; i<=M; i++){
        cin >> S[i] >> E[i] >> W[i];
        G[S[i]].emplace_back(E[i], W[i]);
        G[E[i]].emplace_back(S[i], W[i]);
    }

    for(int i=1; i<=N; i++){
        if(C[i]) continue;
        V.clear(); X.clear(); Y.clear();
        DFS(i, 1, 0);
        if(V.size() == 1) continue;
        sort(X.begin(), X.end());
        X.erase(unique(X.begin(), X.end()), X.end());

        if(X.size() > 1) DIE();
        if(X.size() == 1){
            for(auto j : V) R[j] = A[j].x * X[0] + A[j].y;
        }
        else{
            sort(Y.begin(), Y.end());
            int val = Y[Y.size() / 2];
            for(auto j : V) R[j] = A[j].x * val + 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, ll, ll)':
Graph.cpp:25:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |     for(auto [i,w] : G[v]){
      |              ^

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