oj.uz

Submission #109119

# Submission time Handle Problem Language Result Execution time Memory
109119 2019-05-04T12:35:28 Z ffresh 전압 (JOI14_voltage) C++17
0 / 100
 212 ms 18180 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]);
                ++add2[node];
                ban[id] = true;
                --add2[nextNode];
                ++numOfOddCycle;
            } else {
                //printf("%d %d\n", node,nextNode);
                ++add[node];
                --add[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();
        dp2[curNode] += add2[curNode];
        //printf("%d %d %d %d\n", curNode,parent[curNode], dp[curNode],dp2[curNode]);
        if(dp2[curNode]== numOfOddCycle && dp[curNode]==0 && (parent[curNode]!=0 || (parent[curNode]==0 && dp2[curNode]>0))) {
            //printf("%d\n", curNode);
            ++ret;
        }
        dp[curNode] += add[curNode];
        dp2[parent[curNode]] += dp2[curNode];
        dp[parent[curNode]] += dp[curNode];
    }
    if(numOfOddCycle==1) {
        bool go = true;
        for(int i=1;i<=n;++i) {
            if(!vis[i]) {
                go &= dfs2(i,0);
            }
        }
        if(go) {
            ++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:54: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:73: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:75: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
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 10352 KB Output is correct
2 Correct 123 ms 14300 KB Output is correct
3 Correct 90 ms 10608 KB Output is correct
4 Correct 212 ms 16324 KB Output is correct
5 Correct 17 ms 3840 KB Output is correct
6 Correct 125 ms 12280 KB Output is correct
7 Correct 196 ms 18180 KB Output is correct
8 Incorrect 126 ms 17604 KB Output isn't correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 9840 KB Output is correct
2 Correct 50 ms 17504 KB Output is correct
3 Incorrect 51 ms 17476 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

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