Submission #43279

#	Time	Username	Problem	Language	Result	Execution time	Memory
43279		smu201111192	전압 (JOI14_voltage)	C++14	20 / 100	436 ms	48924 KiB

voltage

#include <iostream>
#include <vector>
#include <cassert>
#include <set>
#include <map>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 200005;
int par[MAXN][20],dep[MAXN],n,m,low[MAXN],dfn[MAXN],step = 0,bridge[MAXN],color[MAXN],tedge[MAXN];
int dp[MAXN],chk[MAXN],pedge[MAXN];
vector<int> bad;
vector<pair<int,int> > adj[MAXN],tree[MAXN];
map<pair<int,int>,vector<int> > mp;
pair<int,int> e[MAXN];
void dfs(int here,int dad,int d,int c){
    dfn[here] = 1;
    color[here] = c;
    dep[here] = d;
    par[here][0] = dad;
    for(int i = 0; i < tree[here].size();i++){
        int there = tree[here][i].first;
        if(there == dad) continue;
        dfs(there,here,d+1,c^1);
    }
}
int getLca(int u,int v){
    if(dep[u] > dep[v]) swap(u,v);
    int diff = dep[v] - dep[u];
    int i = 0;
    while(diff){
        if(diff & (1<<i)) { diff -= (1<<i); v = par[v][i];}
        i++;
    }
    if(u == v)return u;
    for(int i = 19 ; i >=0 ;i--){
        if(par[u][i] != par[v][i]){ u = par[u][i],v = par[v][i]; }
    }
    return par[u][0];
}

int tot = 0;
void getTree(int here,int dad){
    assert(tot<=n);
    low[here] = dfn[here] = ++step;
    for(int i = 0 ; i < adj[here].size();i++){
        if(!dfn[adj[here][i].first]){
            tedge[adj[here][i].second] = 1;
            getTree(adj[here][i].first,here);
            low[here] = min(low[here],low[adj[here][i].first]);
            if(low[adj[here][i].first] > dfn[here])
                bridge[adj[here][i].second] = 1;
        }
        else if(adj[here][i].first != dad && dfn[adj[here][i].first] < dfn[here]){
            low[here] = min(low[here],dfn[adj[here][i].first]);
        }
    }
}
void solve(int here,int dad){
    dfn[here] = 1;
    for(int i = 0; i < tree[here].size(); i++){
        int there = tree[here][i].first;
        int eid = tree[here][i].second;
        if(there == dad) continue;
        pedge[there] = eid;
        solve(there,here);
        dp[here] += dp[there];
    }
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    vector<pair<int,int> > ret;
    for(int i = 1; i <= m; i++){
        int u,v; cin>>u>>v;
        e[i] = make_pair(u,v);
        adj[u].push_back({v,i});
        adj[v].push_back({u,i});
        mp[{min(u,v),max(u,v)}].push_back(i);
    }
    for(int i = 1; i <= n; i++){
        if(!dfn[i]) getTree(i,-1);
    }
    for(int i = 1; i <= m; i++){
        if(tedge[i]){
            int u = e[i].first;
            int v = e[i].second;
            tree[u].push_back({v,i});
            tree[v].push_back({u,i});
            if(mp[{min(u,v),max(u,v)}].size() >= 2) {
                bridge[i] = 0;
            }
        }
    }
    memset(dfn,0,sizeof(dfn));
    for(int i = 1; i <= n; i++){
        if(!dfn[i]) dfs(i,-1,0,0);
    }
    for(int i = 1; i < 20; i++) for(int j = 1; j <= n; j++){
        if(par[j][i-1] == -1) par[j][i] = -1;
        else par[j][i] = par[par[j][i-1]][i-1];
    }
    int bcnt = 0;
    set<int> bbd;
    for(int i = 1; i <= m ;i++) if(bridge[i]) bcnt++;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < adj[i].size(); j++){
            int u = i;
            int v = adj[i][j].first;
            int eid = adj[i][j].second;
            if(tedge[eid]) continue;
            if(color[u] == color[v] && dfn[u] && dfn[v]) bbd.insert(adj[i][j].second);
        }
    }
    bad.assign(bbd.begin(),bbd.end());
    if(bad.size() >= 2){
        cout<<0; exit(0);
    }
    else if(bad.size() == 0){
        cout<<bcnt;
        exit(0);
    }
    else{
        for(int i = 1; i <= m; i++){
            if(!tedge[i]){
                //not tree edge
                int u = e[i].first; int v = e[i].second;
                if(color[u] == color[v]) continue;
                int lca = getLca(u,v);
                vector<int> &vv = mp[{min(u,v),max(u,v)}];
                for(auto x:vv){
                    chk[x] = 1;
                }
                dp[u]++;
                dp[v]++;
                dp[lca] -= 2;
            }
        }
        memset(dfn,0,sizeof(dfn));
        for(int i = 1; i <= n; i++) if(!dfn[i])solve(i,-1);
        for(int i = 1; i <= n; i++){
            if(dp[i] > 0){
                chk[pedge[i]] = 1;  // not bridge면서 !chk 인것들개수
            }
        }
        int ans = 0;
        for(int i = 1; i <= m; i++){
            ans += (!bridge[i] && !chk[i]);
        }
        cout<<ans;
        exit(0);
    }
    return 0;
}

Compilation message (stderr)

voltage.cpp: In function 'void dfs(int, int, int, int)':
voltage.cpp:21:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < tree[here].size();i++){
                      ^
voltage.cpp: In function 'void getTree(int, int)':
voltage.cpp:46:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < adj[here].size();i++){
                       ^
voltage.cpp: In function 'void solve(int, int)':
voltage.cpp:61:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < tree[here].size(); i++){
                      ^
voltage.cpp: In function 'int main()':
voltage.cpp:107:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < adj[i].size(); j++){
                          ^

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 35
• Subtask 4: 0 / 45