oj.uz

Submission #43278

# Submission time Handle Problem Language Result Execution time Memory
43278 2018-03-13T00:45:14 Z smu201111192 전압 (JOI14_voltage) C++14
20 / 100
 391 ms 69164 KB 
#include <iostream>
#include <vector>
#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];
}

void getTree(int here,int dad){
    low[here] = dfn[here] = ++step;
    for(int i = 0 ; i < adj[here].size();i++){
        int there = adj[here][i].first;
        int eid = adj[here][i].second;
        if(!dfn[there]){
            tedge[eid] = 1;
            getTree(there,here);
            low[here] = min(low[here],low[there]);
            tree[here].push_back({there,eid});
            tree[there].push_back({here,eid});
            if(low[there] > dfn[here] && mp[{min(here,there),max(here,there)}].size() <= 1) bridge[eid] = 1;
        }
        else if(there != dad && dfn[there] < dfn[here]){
            low[here] = min(low[here],dfn[there]);
        }
    }
}
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;
        }
    }
    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:20: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:43: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:86:17: warning: unused variable 'u' [-Wunused-variable]
             int u = e[i].first;
                 ^
voltage.cpp:87:17: warning: unused variable 'v' [-Wunused-variable]
             int v = e[i].second;
                 ^
voltage.cpp:102: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 11000 KB Output is correct
2 Correct 10 ms 11000 KB Output is correct
3 Correct 12 ms 11000 KB Output is correct
4 Correct 12 ms 11272 KB Output is correct
5 Correct 11 ms 11480 KB Output is correct
6 Correct 12 ms 11512 KB Output is correct
7 Correct 13 ms 11528 KB Output is correct
8 Correct 13 ms 11528 KB Output is correct
9 Correct 11 ms 11528 KB Output is correct
10 Correct 12 ms 11628 KB Output is correct
11 Correct 13 ms 11644 KB Output is correct
12 Correct 12 ms 11676 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 40604 KB Output is correct
2 Correct 378 ms 49220 KB Output is correct
3 Correct 304 ms 49220 KB Output is correct
4 Correct 361 ms 55484 KB Output is correct
5 Correct 32 ms 55484 KB Output is correct
6 Correct 357 ms 55484 KB Output is correct
7 Correct 326 ms 60972 KB Output is correct
8 Correct 320 ms 61356 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 61356 KB Output is correct
2 Correct 154 ms 62888 KB Output is correct
3 Correct 154 ms 64060 KB Output is correct
4 Correct 10 ms 64060 KB Output is correct
5 Incorrect 242 ms 64060 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 64060 KB Output is correct
2 Correct 214 ms 69164 KB Output is correct
3 Correct 27 ms 69164 KB Output is correct
4 Correct 380 ms 69164 KB Output is correct
5 Correct 391 ms 69164 KB Output is correct
6 Incorrect 350 ms 69164 KB Output isn't correct
7 Halted 0 ms 0 KB -