oj.uz

Submission #43279

# Submission time Handle Problem Language Result Execution time Memory
43279 2018-03-13T00:53:15 Z smu201111192 전압 (JOI14_voltage) C++14
20 / 100
 436 ms 48924 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10872 KB Output is correct
2 Correct 11 ms 10872 KB Output is correct
3 Correct 13 ms 11052 KB Output is correct
4 Correct 11 ms 11052 KB Output is correct
5 Correct 12 ms 11128 KB Output is correct
6 Correct 12 ms 11148 KB Output is correct
7 Correct 16 ms 11276 KB Output is correct
8 Correct 13 ms 11276 KB Output is correct
9 Correct 11 ms 11276 KB Output is correct
10 Correct 11 ms 11328 KB Output is correct
11 Correct 16 ms 11328 KB Output is correct
12 Correct 11 ms 11328 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 40168 KB Output is correct
2 Correct 394 ms 43056 KB Output is correct
3 Correct 281 ms 43056 KB Output is correct
4 Correct 436 ms 45584 KB Output is correct
5 Correct 29 ms 45584 KB Output is correct
6 Correct 379 ms 45584 KB Output is correct
7 Correct 419 ms 46956 KB Output is correct
8 Correct 383 ms 46956 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 46956 KB Output is correct
2 Correct 150 ms 46956 KB Output is correct
3 Correct 161 ms 46956 KB Output is correct
4 Correct 10 ms 46956 KB Output is correct
5 Incorrect 297 ms 46956 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 46956 KB Output is correct
2 Correct 199 ms 48924 KB Output is correct
3 Correct 26 ms 48924 KB Output is correct
4 Correct 415 ms 48924 KB Output is correct
5 Correct 407 ms 48924 KB Output is correct
6 Incorrect 365 ms 48924 KB Output isn't correct
7 Halted 0 ms 0 KB -