Submission #1736297


Source Code Expand

Copy
#include<bits/stdc++.h>

using namespace std;

using int64 = long long;
const int64 UNDEF = 1LL << 61;

struct edge
{
  int to, cost;
};

int N, M;
vector< edge > g[300];
int64 v[300];

int dfs(int idx, int par)
{
  int ret = 0;
  for(auto &e : g[idx]) {
    if(v[e.to] == UNDEF) {
      v[e.to] = v[idx] + e.cost;
      ret += dfs(e.to, par);
    } else if(e.to != par) {
      if(v[idx] + e.cost != v[e.to]) {
        return (114514);
      }
    } else {
      if(v[idx] + e.cost != v[e.to]) {
        ++ret;
      }
    }
  }
  return (ret);
}

int main()
{
  cin >> N >> M;
  for(int i = 0; i < M; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    --a, --b;
    g[a].emplace_back((edge) {b, c});
  }

  for(int i = 0; i < N; i++) {
    fill_n(v, N, UNDEF);
    v[i] = 0;
    if(dfs(i, i) <= 1) {
      cout << "Yes" << endl;
      return (0);
    }
  }
  cout << "No" << endl;
}

Submission Info

Submission Time
Task C - グラフいじり
User ei13333
Language C++14 (GCC 5.4.1)
Score 800
Code Size 940 Byte
Status
Exec Time 136 ms
Memory 1536 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 example_0, example_1, example_2
All 800 / 800 divide2_0, divide2_1, divide2_10, divide2_11, divide2_12, divide2_13, divide2_14, divide2_15, divide2_16, divide2_17, divide2_18, divide2_19, divide2_2, divide2_3, divide2_4, divide2_5, divide2_6, divide2_7, divide2_8, divide2_9, example_0, example_1, example_2, manyerr_0, manyerr_1, manyerr_10, manyerr_11, manyerr_12, manyerr_13, manyerr_14, manyerr_15, manyerr_16, manyerr_17, manyerr_18, manyerr_19, manyerr_2, manyerr_3, manyerr_4, manyerr_5, manyerr_6, manyerr_7, manyerr_8, manyerr_9, rand_0, rand_1, rand_10, rand_11, rand_12, rand_13, rand_14, rand_15, rand_16, rand_17, rand_18, rand_19, rand_2, rand_3, rand_4, rand_5, rand_6, rand_7, rand_8, rand_9, small_0, small_1, small_10, small_11, small_12, small_13, small_14, small_15, small_16, small_17, small_18, small_19, small_2, small_3, small_4, small_5, small_6, small_7, small_8, small_9
Case Name Status Exec Time Memory
divide2_0 47 ms 768 KB
divide2_1 24 ms 384 KB
divide2_10 72 ms 768 KB
divide2_11 3 ms 256 KB
divide2_12 50 ms 768 KB
divide2_13 3 ms 256 KB
divide2_14 79 ms 768 KB
divide2_15 1 ms 256 KB
divide2_16 49 ms 768 KB
divide2_17 2 ms 256 KB
divide2_18 62 ms 768 KB
divide2_19 4 ms 256 KB
divide2_2 112 ms 1408 KB
divide2_3 32 ms 512 KB
divide2_4 51 ms 768 KB
divide2_5 5 ms 256 KB
divide2_6 66 ms 768 KB
divide2_7 5 ms 256 KB
divide2_8 60 ms 768 KB
divide2_9 28 ms 640 KB
example_0 1 ms 256 KB
example_1 1 ms 256 KB
example_2 1 ms 256 KB
manyerr_0 93 ms 1536 KB
manyerr_1 79 ms 896 KB
manyerr_10 91 ms 1536 KB
manyerr_11 54 ms 896 KB
manyerr_12 94 ms 1536 KB
manyerr_13 2 ms 256 KB
manyerr_14 97 ms 1536 KB
manyerr_15 2 ms 256 KB
manyerr_16 94 ms 1536 KB
manyerr_17 3 ms 256 KB
manyerr_18 94 ms 1536 KB
manyerr_19 6 ms 384 KB
manyerr_2 98 ms 1536 KB
manyerr_3 5 ms 384 KB
manyerr_4 93 ms 1536 KB
manyerr_5 58 ms 896 KB
manyerr_6 93 ms 1536 KB
manyerr_7 1 ms 256 KB
manyerr_8 92 ms 1536 KB
manyerr_9 9 ms 384 KB
rand_0 128 ms 1536 KB
rand_1 15 ms 384 KB
rand_10 91 ms 1536 KB
rand_11 3 ms 256 KB
rand_12 127 ms 1536 KB
rand_13 39 ms 768 KB
rand_14 131 ms 1536 KB
rand_15 10 ms 384 KB
rand_16 91 ms 1536 KB
rand_17 3 ms 256 KB
rand_18 136 ms 1536 KB
rand_19 7 ms 384 KB
rand_2 97 ms 1536 KB
rand_3 1 ms 256 KB
rand_4 94 ms 1536 KB
rand_5 15 ms 384 KB
rand_6 88 ms 1536 KB
rand_7 37 ms 640 KB
rand_8 124 ms 1536 KB
rand_9 2 ms 256 KB
small_0 1 ms 256 KB
small_1 1 ms 256 KB
small_10 1 ms 256 KB
small_11 1 ms 256 KB
small_12 1 ms 256 KB
small_13 1 ms 256 KB
small_14 1 ms 256 KB
small_15 1 ms 256 KB
small_16 1 ms 256 KB
small_17 1 ms 256 KB
small_18 1 ms 256 KB
small_19 1 ms 256 KB
small_2 1 ms 256 KB
small_3 1 ms 256 KB
small_4 1 ms 256 KB
small_5 1 ms 256 KB
small_6 1 ms 256 KB
small_7 1 ms 256 KB
small_8 1 ms 256 KB
small_9 1 ms 256 KB