oj.uz

Submission #156081

# Submission time Handle Problem Language Result Execution time Memory
156081 2019-10-03T08:10:37 Z IOrtroiii 전압 (JOI14_voltage) C++14
100 / 100
 173 ms 21080 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 100100;

int n, m;
vector<int> g[N];
vector<int> tr[N];
int cnt[N];
int ds[N];
int bad;

void dfs1(int v, int p) {
   for (int u : g[v]) {
   	if (u == p) p = 0;
    else if (ds[u] && ds[u] < ds[v])  {
    	// printf("back edge %d -> %d\n", v, u);
        if ((ds[v] & 1) == (ds[u] & 1)) {
           ++bad;
           cnt[v]++;
           cnt[u]--;
        } else {
           cnt[v]--;
           cnt[u]++;
        }
    } else if (!ds[u]) {
        ds[u] = ds[v] + 1;
        tr[v].emplace_back(u);
        // printf("tree edge %d -> %d\n", v, u);
        dfs1(u, v);
    }
   }
}

void dfs2(int v) {
   for (int u : tr[v]) {
      dfs2(u);
      cnt[v] += cnt[u];
   }
}

int main() {
   scanf("%d %d", &n, &m);
   for (int i = 1; i <= m; ++i) {
      int v, u;
      scanf("%d %d", &v, &u);
      g[v].emplace_back(u);
      g[u].emplace_back(v);
   }
   for (int i = 1; i <= n; ++i) {
      if (!ds[i]) {
         ds[i] = 1;
         dfs1(i, -1);
      }
   }
   for (int i = 1; i <= n; ++i) {
      if (ds[i] == 1) {
         dfs2(i);
      }
   }
   int ans = 0;
   for (int i = 1; i <= n; ++i) {
      if (ds[i] > 1 && cnt[i] == bad) {
         ++ans;
      }
   }
   // printf("%d\n", bad);
   ans += (bad == 1);
   printf("%d\n", ans);
}

Compilation message

voltage.cpp: In function 'int main()':
voltage.cpp:44:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &n, &m);
    ~~~~~^~~~~~~~~~~~~~~~~
voltage.cpp:47:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &v, &u);
       ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5116 KB Output is correct
2 Correct 6 ms 4984 KB Output is correct
3 Correct 6 ms 4984 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Correct 7 ms 5112 KB Output is correct
7 Correct 7 ms 5112 KB Output is correct
8 Correct 7 ms 5112 KB Output is correct
9 Correct 7 ms 5112 KB Output is correct
10 Correct 7 ms 5112 KB Output is correct
11 Correct 7 ms 5240 KB Output is correct
12 Correct 7 ms 5112 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 9712 KB Output is correct
2 Correct 87 ms 16504 KB Output is correct
3 Correct 54 ms 9712 KB Output is correct
4 Correct 97 ms 18296 KB Output is correct
5 Correct 13 ms 5880 KB Output is correct
6 Correct 91 ms 13252 KB Output is correct
7 Correct 99 ms 21080 KB Output is correct
8 Correct 94 ms 20984 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 9584 KB Output is correct
2 Correct 59 ms 19964 KB Output is correct
3 Correct 62 ms 19896 KB Output is correct
4 Correct 6 ms 4984 KB Output is correct
5 Correct 77 ms 14044 KB Output is correct
6 Correct 81 ms 10704 KB Output is correct
7 Correct 90 ms 14968 KB Output is correct
8 Correct 96 ms 18424 KB Output is correct
9 Correct 108 ms 17400 KB Output is correct
10 Correct 93 ms 15764 KB Output is correct
11 Correct 84 ms 11824 KB Output is correct
12 Correct 98 ms 14456 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 10640 KB Output is correct
2 Correct 87 ms 19832 KB Output is correct
3 Correct 7 ms 5368 KB Output is correct
4 Correct 109 ms 15828 KB Output is correct
5 Correct 111 ms 17144 KB Output is correct
6 Correct 118 ms 15480 KB Output is correct
7 Correct 151 ms 15608 KB Output is correct
8 Correct 158 ms 19420 KB Output is correct
9 Correct 146 ms 16548 KB Output is correct
10 Correct 149 ms 19484 KB Output is correct
11 Correct 159 ms 16504 KB Output is correct
12 Correct 173 ms 19448 KB Output is correct
13 Correct 142 ms 15952 KB Output is correct
14 Correct 153 ms 20824 KB Output is correct
15 Correct 168 ms 19488 KB Output is correct
16 Correct 146 ms 18828 KB Output is correct
17 Correct 145 ms 15956 KB Output is correct
18 Correct 118 ms 16028 KB Output is correct