oj.uz

Submission #581985

# Submission time Handle Problem Language Result Execution time Memory
581985 2022-06-23T09:13:03 Z 박상훈(#8364) 전압 (JOI14_voltage) C++14
45 / 100
 1000 ms 23220 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
const int INF = 1e9;
vector<pair<int, int>> adj[100100], G0[100100];
pair<int, int> E[200200];
int n, m, C[200200];
bool visited[200200], is_dfs[200200];

void dfs0(int s, int pa_edge = -1){
    visited[s] = 1;
    for (auto &[v, i]:adj[s]) if (i!=pa_edge){
        if (visited[v]) continue;
        is_dfs[i] = 1;
        G0[s].emplace_back(v, i);
        G0[v].emplace_back(s, i);
        dfs0(v, i);
    }
}

vector<int> st;
bool dfs1(int s, int e, int pa = -1){
    if (s==e) return 1;

    for (auto &[v, i]:G0[s]) if (v!=pa){
        st.push_back(i);
        if (dfs1(v, e, s)) return 1;
        st.pop_back();
    }

    return 0;
}

void sol3(){
    dfs0(1);
    int odd_cnt = 0;
    for (int i=1;i<=m;i++) if (!is_dfs[i]){
        //printf("YES\n");
        st.clear();
        dfs1(E[i].first, E[i].second);
        int c = (st.size()&1) ^ 1;

        if (c==1) odd_cnt++;
        for (auto &j:st){
            //printf(" %d %d: %d\n", i, c, j);
            if (c==1) C[j]++;
            else C[j] = -INF;
        }
    }

    /*printf(" %d\n", odd_cnt);
    for (int i=1;i<=m;i++) printf("%d ", is_dfs[i]);
    printf("\n");
    for (int i=1;i<=m;i++) printf("%d ", C[i]);
    printf("\n");*/

    int ans = (odd_cnt==1);
    for (int i=1;i<=m;i++) if (C[i]==odd_cnt && is_dfs[i]) ans++;
    printf("%d\n", ans);
}

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

    //if (n<=1000) naive();

    //sol2();
    sol3();
    return 0;
}


/*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);
}

vector<int> cyc;
int dfs_cyc(int s, int pa = -1){
    visited[s] = 1;
    cyc.push_back(s);

    int pacnt = 0;
    for (auto &v:adj[s]){
        if (v==pa){
            pacnt++;
            if (pacnt==1) continue;
        }

        if (visited[v]>=0){
            return v;
        }
        int tmp = dfs_cyc(v, s);
        if (tmp>=0) return tmp;
    }
    cyc.pop_back();
    return -1;
}

void sol2(){
    fill(visited+1, visited+n+1, -1);
    int t = dfs_cyc(1), len = -1;

    assert(t!=-1);
    for (int i=(int)cyc.size()-1;i>=0;i--) if (cyc[i]==t){
        len = (int)cyc.size() - i;
        break;
    }
    //for (auto &x:cyc) printf(" %d", x);
    //printf(" / %d\n", t);
    assert(len!=-1);

    if (len%2==0) printf("%d\n", m - len);
    else printf("%d\n", len);
}*/

Compilation message

voltage.cpp: In function 'void dfs0(int, int)':
voltage.cpp:13:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   13 |     for (auto &[v, i]:adj[s]) if (i!=pa_edge){
      |                ^
voltage.cpp: In function 'bool dfs1(int, int, int)':
voltage.cpp:26:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |     for (auto &[v, i]:G0[s]) if (v!=pa){
      |                ^
voltage.cpp: In function 'int main()':
voltage.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
voltage.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5152 KB Output is correct
2 Correct 3 ms 5020 KB Output is correct
3 Correct 5 ms 5016 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 9 ms 5204 KB Output is correct
6 Correct 7 ms 5204 KB Output is correct
7 Correct 9 ms 5148 KB Output is correct
8 Incorrect 4 ms 5076 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 14936 KB Output is correct
2 Correct 86 ms 18348 KB Output is correct
3 Correct 56 ms 14716 KB Output is correct
4 Correct 88 ms 20268 KB Output is correct
5 Correct 8 ms 6424 KB Output is correct
6 Correct 103 ms 17740 KB Output is correct
7 Correct 102 ms 23220 KB Output is correct
8 Correct 93 ms 23188 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 14524 KB Output is correct
2 Correct 43 ms 21676 KB Output is correct
3 Correct 46 ms 21764 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 203 ms 16676 KB Output is correct
6 Correct 87 ms 13488 KB Output is correct
7 Correct 245 ms 18224 KB Output is correct
8 Correct 269 ms 19752 KB Output is correct
9 Correct 215 ms 19580 KB Output is correct
10 Correct 234 ms 17628 KB Output is correct
11 Correct 136 ms 14108 KB Output is correct
12 Correct 148 ms 16056 KB Output is correct

Subtask #4
0 / 45.0

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