oj.uz

Submission #581733

# Submission time Handle Problem Language Result Execution time Memory
581733 2022-06-23T05:21:25 Z 박상훈(#8364) 전압 (JOI14_voltage) C++14
10 / 100
 107 ms 8036 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
vector<int> adj[100100];
pair<int, int> E[200200];
int n, m, visited[200200];

bool dfs_col(int s, int c = 0){
    visited[s] = c;
    for (auto &v:adj[s]){
        if (visited[v]<0){
            if (!dfs_col(v, c^1)) return 0;
        }
        else if (visited[v]==c) return 0;
    }
    return 1;
}

void naive(){
    int ans = 0;
    for (int i=1;i<=m;i++){
        for (int j=1;j<=n;j++) adj[j].clear();
        for (int j=1;j<=m;j++) if (i!=j){
            adj[E[j].first].push_back(E[j].second);
            adj[E[j].second].push_back(E[j].first);
        }

        fill(visited+1, visited+n+1, -1);
        visited[E[i].first] = visited[E[i].second] = 0;
        bool flag = 1;
        flag &= dfs_col(E[i].first);
        flag &= dfs_col(E[i].second);

        for (int j=1;j<=n;j++) if (visited[j]<0) flag &= dfs_col(j);
        if (flag) ans++;
    }
    printf("%d\n", ans);
    exit(0);
}

int main(){
    scanf("%d %d", &n, &m);
    for (int i=1;i<=m;i++){
        int x, y;
        scanf("%d %d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
        E[i] = {x, y};
    }

    if (n<=1000) naive();

    return 0;
}

Compilation message

voltage.cpp: In function 'int main()':
voltage.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
voltage.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 2644 KB Output is correct
2 Correct 55 ms 2644 KB Output is correct
3 Correct 47 ms 2644 KB Output is correct
4 Correct 28 ms 2692 KB Output is correct
5 Correct 97 ms 2732 KB Output is correct
6 Correct 91 ms 2768 KB Output is correct
7 Correct 93 ms 2732 KB Output is correct
8 Correct 90 ms 2712 KB Output is correct
9 Correct 80 ms 2720 KB Output is correct
10 Correct 101 ms 2740 KB Output is correct
11 Correct 107 ms 2644 KB Output is correct
12 Correct 105 ms 2732 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 6952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 6940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 8036 KB Output isn't correct
2 Halted 0 ms 0 KB -