Submission #237615

#	Time	Username	Problem	Language	Result	Execution time	Memory
237615		nickmet2004	One-Way Streets (CEOI17_oneway)	C++11	0 / 100	7 ms	5504 KiB

oneway

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
typedef pair<int , int> ipair;

int n , m;
vector<ipair> adj[N] , G[N];
ipair edges[N];
int vis[N] , low[N] , disc[N] , bridges[N] , comp[N] , sum[N];
char ans[N];
map<ipair , int> mp;

int dtime = 0;
void dfs(int u , int p){
    disc[u] = low[u] = dtime++; vis[u]=1;
    for(ipair x : adj[u]){
        int v = x.first , id = x.second;
        if(!vis[v]){
            dfs(v , u);
            if(disc[u] < low[v]) bridges[id]=1;
            low[u] = min(low[u] , low[v]);
        }else if(v ^ p) low[u] = min(low[u] , disc[v]);
    }
}
void component(int u , int x){
    vis[u] = 1; comp[u] = x;
    for(ipair X : adj[u]){
        int v = X.first , id = X.second;
        if(!vis[v] && !bridges[id]) component(v , x);
    }
}
void go(int u , int p){
    if(vis[u]) return;
    vis[u]=1;
    for(ipair x : G[u]){
        int v = x.first , id = x.second;
        if(v==p) continue;
        go(v , u);
        //cout << sum[u]  << " sumu " << endl;
        if(sum[v] > 0){
            if(mp[{edges[id].first , edges[id].second}]) ans[id] = 'R'; else ans[id] = 'L';
        }
        if(sum[v] < 0){
            if(mp[{edges[id].first , edges[id].second}]) ans[id] = 'L'; else ans[id] = 'R';
        }
        sum[u] += sum[v];
    }
}
int main (){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < m; ++i){
        int u , v;
        cin >> u >> v; --u; --v;
        adj[u].emplace_back(v , i); adj[v].emplace_back(u , i);
        edges[i].first = u;edges[i].second = v; mp[{u , v}]++;
    }
    memset(vis , 0 , sizeof(vis));
    for(int i = 0; i < n; ++i){if(!vis[i]) dfs(i , -1);}
    //for(int i = 0; i < m; ++i) if(bridges[i])cout <<i <<  " yes " << endl;
    int c=0;
    memset(vis , 0 , sizeof(vis));
    for(int i = 0; i < n; ++i){
        if(!vis[i]){component(i , c); c++;}
    }
  //  cerr << c<< " C " << endl;
    for(int i = 0; i < m; ++i){
        int cu = comp[edges[i].first] , cv = comp[edges[i].second];
       // cerr << cu << " cu " << cv << " cv " << endl;
        if(bridges[i]){G[cu].emplace_back(cv , i); G[cv].emplace_back(cu , i);}
    }
    for(int i = 0; i < c; ++i){
       // for(ipair v : G[i]) cout << v.first << " "; cerr << endl;
    }
    int p;
    cin >> p;
    while(p--){
        int u , v; cin >> u >> v; --u; --v;
        sum[comp[u]]++; sum[comp[v]]--;
       // cout << comp[u] << "compu " << comp[v] << " compv " << endl;
        cout << sum[comp[v]] <<endl;
    }
    memset(vis , 0 , sizeof(vis));
    for(int i = 0; i < c; ++i)go(i , -1);
    for(int i = 0; i < m; ++i)if(ans[i] != 'L' && ans[i] != 'R') ans[i] = 'B'; cout << ans;
return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:87:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int i = 0; i < m; ++i)if(ans[i] != 'L' && ans[i] != 'R') ans[i] = 'B'; cout << ans;
     ^~~
oneway.cpp:87:80: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(int i = 0; i < m; ++i)if(ans[i] != 'L' && ans[i] != 'R') ans[i] = 'B'; cout << ans;
                                                                                ^~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40