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 AC
Exec Time 136 ms
Memory 1536 KB

Judge Result

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