oj.uz

Submission #109121

# Submission time Handle Problem Language Result Execution time Memory
109121 2019-05-04T12:49:33 Z ffresh 전압 (JOI14_voltage) C++17
100 / 100
 245 ms 19564 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 1e5+15;
const int M = 2e5+15;

int dp[N],dp2[N],add[N],add2[N];
vector<int> adj[N];

int a[M],b[M];

int depth[N],parent[N];

int numOfOddCycle = 0;

stack<int> st;
bool ban[M];
vector<pair<int,int> > g;
void dfs(int node,int prevEdge,int curDep) {
    depth[node] = curDep;
    st.push(node);
    for(int i=0;i<adj[node].size(); ++i) {
        int id = adj[node][i];
        if(id == prevEdge) {
            continue;
        }
        int nextNode = a[id]^b[id]^node;
        if(depth[nextNode]==0 ){
            parent[nextNode] = node;
            dfs(nextNode,id,curDep+1);
        } else if(depth[nextNode] <depth[node]){
            if(depth[nextNode]%2== depth[node]%2) {
                //printf("%d %d\n", depth[nextNode],depth[node]);
                ++dp2[node];
                --dp2[nextNode];
                ++numOfOddCycle;
            } else {
                //printf("%d %d\n", node,nextNode);
                ++dp[node];
                --dp[nextNode];
            }
        }
    }
}

bool vis[N];

int color[N];
bool dfs2(int node,int c) {
    vis[node] = true;
    color[node] = c;
    for(int i=0;i<adj[node].size();++i) {
        int id = adj[node][i];
        if(ban[id]) {
            continue;
        }
        int ch = a[id]^b[id]^node;
        if(!vis[ch]) {
            dfs2(ch,c^1);
        } else {
            if(color[node]==color[ch]){
                return false;
            }
        }
    }
    return true;
}

void solve() {
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;++i) {
        scanf("%d%d",&a[i],&b[i]);
        adj[a[i]].push_back(i);
        adj[b[i]].push_back(i);
    }
    for(int i=1;i<=n;++i ){
        if(depth[i]==0) {
            dfs(i,-1,1);
        }
    }
    int ret = 0;
    //printf("%d\n", numOfOddCycle);
    while(!st.empty()) {
        int curNode = st.top();
        st.pop();
        //printf("%d %d %d %d\n", curNode,parent[curNode], dp[curNode],dp2[curNode]);
        if(dp2[curNode]== numOfOddCycle && dp[curNode]==0 && parent[curNode]!=0 ) {
            //printf("%d\n", curNode);
            ++ret;
        }
        dp2[parent[curNode]] += dp2[curNode];
        dp[parent[curNode]] += dp[curNode];
    }
    if(numOfOddCycle==1) {
        ++ret;
    }

    printf("%d\n", ret);
}

int main() {
    //freopen("input.txt","r",stdin);
    solve();
}

Compilation message

voltage.cpp: In function 'void dfs(int, int, int)':
voltage.cpp:23:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<adj[node].size(); ++i) {
                 ~^~~~~~~~~~~~~~~~~
voltage.cpp: In function 'bool dfs2(int, int)':
voltage.cpp:53:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<adj[node].size();++i) {
                 ~^~~~~~~~~~~~~~~~~
voltage.cpp: In function 'void solve()':
voltage.cpp:72: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:74:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a[i],&b[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2816 KB Output is correct
2 Correct 6 ms 2816 KB Output is correct
3 Correct 5 ms 2816 KB Output is correct
4 Correct 5 ms 2816 KB Output is correct
5 Correct 6 ms 2816 KB Output is correct
6 Correct 7 ms 2944 KB Output is correct
7 Correct 6 ms 2816 KB Output is correct
8 Correct 5 ms 2816 KB Output is correct
9 Correct 7 ms 2920 KB Output is correct
10 Correct 7 ms 2816 KB Output is correct
11 Correct 6 ms 2864 KB Output is correct
12 Correct 5 ms 2816 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 8276 KB Output is correct
2 Correct 112 ms 13072 KB Output is correct
3 Correct 61 ms 8204 KB Output is correct
4 Correct 98 ms 14840 KB Output is correct
5 Correct 10 ms 3584 KB Output is correct
6 Correct 105 ms 11128 KB Output is correct
7 Correct 138 ms 16384 KB Output is correct
8 Correct 123 ms 16376 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 8148 KB Output is correct
2 Correct 49 ms 16452 KB Output is correct
3 Correct 53 ms 16324 KB Output is correct
4 Correct 5 ms 2688 KB Output is correct
5 Correct 113 ms 12252 KB Output is correct
6 Correct 110 ms 9980 KB Output is correct
7 Correct 116 ms 13276 KB Output is correct
8 Correct 121 ms 15096 KB Output is correct
9 Correct 127 ms 14556 KB Output is correct
10 Correct 131 ms 12896 KB Output is correct
11 Correct 104 ms 9848 KB Output is correct
12 Correct 128 ms 11768 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 9808 KB Output is correct
2 Correct 79 ms 19564 KB Output is correct
3 Correct 9 ms 3456 KB Output is correct
4 Correct 129 ms 14328 KB Output is correct
5 Correct 126 ms 15736 KB Output is correct
6 Correct 131 ms 14064 KB Output is correct
7 Correct 229 ms 16212 KB Output is correct
8 Correct 187 ms 17016 KB Output is correct
9 Correct 198 ms 14712 KB Output is correct
10 Correct 224 ms 17656 KB Output is correct
11 Correct 154 ms 14984 KB Output is correct
12 Correct 242 ms 17800 KB Output is correct
13 Correct 179 ms 14444 KB Output is correct
14 Correct 186 ms 18764 KB Output is correct
15 Correct 216 ms 17784 KB Output is correct
16 Correct 245 ms 17296 KB Output is correct
17 Correct 176 ms 14960 KB Output is correct
18 Correct 144 ms 15060 KB Output is correct