oj.uz

답안 #581987

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
581987 2022-06-23T09:14:14 Z 박상훈(#8364) 전압 (JOI14_voltage) C++14
55 / 100
 1000 ms 22496 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(){
    for (int i=1;i<=n;i++) if (!visited[i]) dfs0(i);
    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
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5204 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 4 ms 5076 KB Output is correct
5 Correct 9 ms 5076 KB Output is correct
6 Correct 8 ms 5204 KB Output is correct
7 Correct 9 ms 5212 KB Output is correct
8 Correct 5 ms 5076 KB Output is correct
9 Correct 5 ms 5076 KB Output is correct
10 Correct 11 ms 5204 KB Output is correct
11 Correct 9 ms 5204 KB Output is correct
12 Correct 10 ms 5152 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 13776 KB Output is correct
2 Correct 102 ms 17544 KB Output is correct
3 Correct 50 ms 13760 KB Output is correct
4 Correct 108 ms 19560 KB Output is correct
5 Correct 12 ms 6228 KB Output is correct
6 Correct 90 ms 16956 KB Output is correct
7 Correct 88 ms 22496 KB Output is correct
8 Correct 95 ms 22472 KB Output is correct

Subtask #3
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 13760 KB Output is correct
2 Correct 49 ms 21544 KB Output is correct
3 Correct 47 ms 21644 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 175 ms 16636 KB Output is correct
6 Correct 88 ms 13380 KB Output is correct
7 Correct 328 ms 18128 KB Output is correct
8 Correct 334 ms 19572 KB Output is correct
9 Correct 223 ms 19460 KB Output is correct
10 Correct 226 ms 17520 KB Output is correct
11 Correct 164 ms 13772 KB Output is correct
12 Correct 208 ms 15904 KB Output is correct

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1090 ms 15436 KB Time limit exceeded
2 Halted 0 ms 0 KB -