oj.uz

Submission #129760

# Submission time Handle Problem Language Result Execution time Memory
129760 2019-07-13T07:31:20 Z 송준혁(#3142) 전압 (JOI14_voltage) C++14
10 / 100
 1000 ms 7896 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 col[101010];

bool dfs(int u, int b, int c){
    if (col[u]){
        if (col[u] != c) return false;
        return true;
    }
    col[u] = c;
    for (pii v : adj[u]){
        if (v.second == b){
            if (!dfs(v.first, b, c)) return false;
        }
        else if (!dfs(v.first, b, c*-1)) return false;
    }
    return true;
}

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));
    }
    for (int i=1; i<=M; i++){
        memset(col, 0, sizeof col);
        bool tf = true;
        for (int j=1; j<=N; j++) if (!col[j]) tf = tf && dfs(j, i, 1);
        if (tf) ans++;
    }
    printf("%d\n", ans);
    return 0;
}

Compilation message

voltage.cpp: In function 'int main()':
voltage.cpp:27: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:29: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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 3256 KB Output is correct
2 Correct 60 ms 3344 KB Output is correct
3 Correct 45 ms 3064 KB Output is correct
4 Correct 40 ms 3196 KB Output is correct
5 Correct 81 ms 3192 KB Output is correct
6 Correct 98 ms 3320 KB Output is correct
7 Correct 87 ms 3192 KB Output is correct
8 Correct 67 ms 3320 KB Output is correct
9 Correct 73 ms 3192 KB Output is correct
10 Correct 80 ms 3236 KB Output is correct
11 Correct 63 ms 3320 KB Output is correct
12 Correct 79 ms 3192 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 35.0

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

Subtask #4
0 / 45.0

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