Submission #109121

#	Time	Username	Problem	Language	Result	Execution time	Memory
109121		ffresh	전압 (JOI14_voltage)	C++17	100 / 100	245 ms	19564 KiB

voltage

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 35 / 35
• Subtask 4: 45 / 45