oj.uz

Submission #447290

# Submission time Handle Problem Language Result Execution time Memory
447290 2021-07-25T20:27:16 Z jhnah917 Graph (BOI20_graph) C++14
0 / 100
 2 ms 2700 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2700 KB answer = YES
2 Correct 2 ms 2636 KB answer = YES
3 Correct 2 ms 2636 KB answer = YES
4 Correct 2 ms 2636 KB answer = NO
5 Correct 2 ms 2636 KB answer = YES
6 Correct 2 ms 2636 KB answer = YES
7 Correct 2 ms 2696 KB answer = YES
8 Correct 2 ms 2636 KB answer = YES
9 Correct 2 ms 2636 KB answer = NO
10 Correct 2 ms 2636 KB answer = YES
11 Correct 2 ms 2636 KB answer = YES
12 Correct 2 ms 2636 KB answer = NO
13 Correct 2 ms 2636 KB answer = YES
14 Correct 2 ms 2636 KB answer = YES
15 Correct 2 ms 2636 KB answer = YES
16 Correct 2 ms 2636 KB answer = YES
17 Correct 2 ms 2636 KB answer = YES
18 Incorrect 2 ms 2636 KB Sum of endpoints for edge (1; 1) differs from the expected value 1.
19 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2700 KB answer = YES
2 Correct 2 ms 2636 KB answer = YES
3 Correct 2 ms 2636 KB answer = YES
4 Correct 2 ms 2636 KB answer = NO
5 Correct 2 ms 2636 KB answer = YES
6 Correct 2 ms 2636 KB answer = YES
7 Correct 2 ms 2696 KB answer = YES
8 Correct 2 ms 2636 KB answer = YES
9 Correct 2 ms 2636 KB answer = NO
10 Correct 2 ms 2636 KB answer = YES
11 Correct 2 ms 2636 KB answer = YES
12 Correct 2 ms 2636 KB answer = NO
13 Correct 2 ms 2636 KB answer = YES
14 Correct 2 ms 2636 KB answer = YES
15 Correct 2 ms 2636 KB answer = YES
16 Correct 2 ms 2636 KB answer = YES
17 Correct 2 ms 2636 KB answer = YES
18 Incorrect 2 ms 2636 KB Sum of endpoints for edge (1; 1) differs from the expected value 1.
19 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2700 KB answer = YES
2 Correct 2 ms 2636 KB answer = YES
3 Correct 2 ms 2636 KB answer = YES
4 Correct 2 ms 2636 KB answer = NO
5 Correct 2 ms 2636 KB answer = YES
6 Correct 2 ms 2636 KB answer = YES
7 Correct 2 ms 2696 KB answer = YES
8 Correct 2 ms 2636 KB answer = YES
9 Correct 2 ms 2636 KB answer = NO
10 Correct 2 ms 2636 KB answer = YES
11 Correct 2 ms 2636 KB answer = YES
12 Correct 2 ms 2636 KB answer = NO
13 Correct 2 ms 2636 KB answer = YES
14 Correct 2 ms 2636 KB answer = YES
15 Correct 2 ms 2636 KB answer = YES
16 Correct 2 ms 2636 KB answer = YES
17 Correct 2 ms 2636 KB answer = YES
18 Incorrect 2 ms 2636 KB Sum of endpoints for edge (1; 1) differs from the expected value 1.
19 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2700 KB answer = YES
2 Correct 2 ms 2636 KB answer = YES
3 Correct 2 ms 2636 KB answer = YES
4 Correct 2 ms 2636 KB answer = NO
5 Correct 2 ms 2636 KB answer = YES
6 Correct 2 ms 2636 KB answer = YES
7 Correct 2 ms 2696 KB answer = YES
8 Correct 2 ms 2636 KB answer = YES
9 Correct 2 ms 2636 KB answer = NO
10 Correct 2 ms 2636 KB answer = YES
11 Correct 2 ms 2636 KB answer = YES
12 Correct 2 ms 2636 KB answer = NO
13 Correct 2 ms 2636 KB answer = YES
14 Correct 2 ms 2636 KB answer = YES
15 Correct 2 ms 2636 KB answer = YES
16 Correct 2 ms 2636 KB answer = YES
17 Correct 2 ms 2636 KB answer = YES
18 Incorrect 2 ms 2636 KB Sum of endpoints for edge (1; 1) differs from the expected value 1.
19 Halted 0 ms 0 KB -

Subtask #5
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2700 KB answer = YES
2 Correct 2 ms 2636 KB answer = YES
3 Correct 2 ms 2636 KB answer = YES
4 Correct 2 ms 2636 KB answer = NO
5 Correct 2 ms 2636 KB answer = YES
6 Correct 2 ms 2636 KB answer = YES
7 Correct 2 ms 2696 KB answer = YES
8 Correct 2 ms 2636 KB answer = YES
9 Correct 2 ms 2636 KB answer = NO
10 Correct 2 ms 2636 KB answer = YES
11 Correct 2 ms 2636 KB answer = YES
12 Correct 2 ms 2636 KB answer = NO
13 Correct 2 ms 2636 KB answer = YES
14 Correct 2 ms 2636 KB answer = YES
15 Correct 2 ms 2636 KB answer = YES
16 Correct 2 ms 2636 KB answer = YES
17 Correct 2 ms 2636 KB answer = YES
18 Incorrect 2 ms 2636 KB Sum of endpoints for edge (1; 1) differs from the expected value 1.
19 Halted 0 ms 0 KB -