oj.uz

Submission #129756

# Submission time Handle Problem Language Result Execution time Memory
129756 2019-07-13T07:22:27 Z 송준혁(#3142) 전압 (JOI14_voltage) C++14
10 / 100
 1000 ms 12636 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int N, M, O, ans;
vector<pii> adj[101010];
int P[101010], E[101010], cnt[101010], num;
bool chk[101010];

void dfs(int u){
    if (P[u] != -1){
        if ((num - P[u]) & 1){
            O++;
            for (int i=P[u]+1; i<=num; i++) cnt[E[i]]++;
        }
        else for (int i=P[u]+1; i<=num; i++) chk[E[i]] = true;
        return;
    }
    P[u] = num;
    for (pii v : adj[u]){
        if (v.second == E[num]) continue;
        E[++num] = v.second;
        dfs(v.first);
        num--;
    }
    P[u] = -1;
}

int main(){
    int u, v;
    scanf("%d %d", &N, &M);
    for (int i=1; i<=M; i++){
        scanf("%d %d", &u, &v);
        adj[u].push_back(pii(v, i));
        adj[v].push_back(pii(u, i));
    }
    memset(P, -1, sizeof P);
    dfs(1);
    for (int i=1; i<=M; i++) if (!chk[i]) ans += O == cnt[i];
    printf("%d\n", ans);
    return 0;
}

Compilation message

voltage.cpp: In function 'int main()':
voltage.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~~
voltage.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 3192 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 7788 KB Output is correct
2 Correct 89 ms 9032 KB Output is correct
3 Correct 47 ms 7788 KB Output is correct
4 Correct 84 ms 9720 KB Output is correct
5 Correct 11 ms 3704 KB Output is correct
6 Correct 77 ms 8824 KB Output is correct
7 Correct 98 ms 11036 KB Output is correct
8 Correct 121 ms 10648 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 7788 KB Output is correct
2 Correct 45 ms 10576 KB Output is correct
3 Execution timed out 1073 ms 10488 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 9316 KB Output is correct
2 Execution timed out 1075 ms 12636 KB Time limit exceeded
3 Halted 0 ms 0 KB -