oj.uz

Submission #657470

# Submission time Handle Problem Language Result Execution time Memory
657470 2022-11-09T23:38:48 Z perchuts One-Way Streets (CEOI17_oneway) C++17
100 / 100
 102 ms 21232 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define endl '\n'
#define _ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
 
using namespace std;
 
using ii = pair<int,int>;
using iii = tuple<int,int,int>;
using ll = long long;
 
const int inf = 1e9+1;
const int mod = 1e9+7;
const int maxn = 2e5+100;
 
template<typename X,typename Y> bool ckmin(X& x,Y y){return (x>y?x=y,1:0);}
template<typename X,typename Y> bool ckmax(X& x,Y y){return (x<y?x=y,1:0);}
 
vector<ii>g[maxn];
 
int dp[maxn], lvl[maxn], entrada[maxn], saida[maxn], bridge[maxn], vis[maxn], t = 0;
ii ranges[maxn][2];
 
void dfs(int u,int p){
    lvl[u] = lvl[p] + 1, entrada[u] = ++t;
    for(auto [v,idx]:g[u]){
        if(!lvl[v]){
            dfs(v,u);
            dp[u] += dp[v];
        }
        else if(lvl[u]<lvl[v]) --dp[u];
        else if(lvl[u]>lvl[v]) ++dp[u];
    }
    dp[u]--; 
    bridge[u] = (dp[u]==0&&u!=1), saida[u] = ++t;
}
 
string ans;
vector<ii>edges;
 
void dfs2(int u,int p,int cur){
    vis[u] = 1;
    for(auto [v,idx]:g[u]){
        if(vis[v])continue;
        dfs2(v,u,idx);
        ckmin(ranges[u][0].first, ranges[v][0].first),ckmin(ranges[u][1].first, ranges[v][1].first);
        ckmax(ranges[u][0].second, ranges[v][0].second),ckmax(ranges[u][1].second, ranges[v][1].second);
    }
    if(bridge[u]){
        bool ok = 0;
        if(ranges[u][0]!=make_pair(entrada[u],saida[u])){//u->p
            ans[cur] = (edges[cur].first==u?'R':'L'), ok = 1;
        }
        if(ranges[u][1]!=make_pair(entrada[u],saida[u])){//u<-p
            assert(ok==0);//impossivel os 2 acontecerem juntos
            ans[cur] = (edges[cur].first==u?'L':'R');
        }
    }
}
 
int main(){_
    int n,m,p;cin>>n>>m;
 
    ans.resize(m, 'B');
 
    for(int i=0;i<m;++i){
        int u,v;cin>>u>>v;
        edges.pb({u,v});
        if(u==v)continue;//self loops are allowed!
        g[u].pb({v,i}), g[v].pb({u,i});
    }
    for(int i=1;i<=n;++i){
        if(!lvl[i])dfs(i,i);
    }
 
    for(int i=1;i<=n;++i) ranges[i][1] = ranges[i][0] = {entrada[i], saida[i]};
 
    cin>>p;
 
    vector<ii>pairs(p);
 
    for(auto& [x,y]:pairs){
        cin>>x>>y;
        ckmin(ranges[x][0].first, entrada[y]), ckmax(ranges[x][0].second, entrada[y]);
        ckmin(ranges[y][1].first, entrada[x]), ckmax(ranges[y][1].second, entrada[x]);
    }

    for(int i=1;i<=n;++i){
        if(!vis[i])dfs2(i,i,0);
    }
    
    cout<<ans<<endl;
 
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5040 KB Output is correct
5 Correct 4 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5040 KB Output is correct
5 Correct 4 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct
11 Correct 33 ms 11720 KB Output is correct
12 Correct 42 ms 12932 KB Output is correct
13 Correct 64 ms 14592 KB Output is correct
14 Correct 60 ms 16068 KB Output is correct
15 Correct 58 ms 16304 KB Output is correct
16 Correct 55 ms 14776 KB Output is correct
17 Correct 51 ms 16372 KB Output is correct
18 Correct 57 ms 14832 KB Output is correct
19 Correct 65 ms 17432 KB Output is correct
20 Correct 39 ms 13144 KB Output is correct
21 Correct 36 ms 12768 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5040 KB Output is correct
5 Correct 4 ms 5076 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5076 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct
11 Correct 33 ms 11720 KB Output is correct
12 Correct 42 ms 12932 KB Output is correct
13 Correct 64 ms 14592 KB Output is correct
14 Correct 60 ms 16068 KB Output is correct
15 Correct 58 ms 16304 KB Output is correct
16 Correct 55 ms 14776 KB Output is correct
17 Correct 51 ms 16372 KB Output is correct
18 Correct 57 ms 14832 KB Output is correct
19 Correct 65 ms 17432 KB Output is correct
20 Correct 39 ms 13144 KB Output is correct
21 Correct 36 ms 12768 KB Output is correct
22 Correct 73 ms 18204 KB Output is correct
23 Correct 87 ms 16608 KB Output is correct
24 Correct 102 ms 16748 KB Output is correct
25 Correct 78 ms 21232 KB Output is correct
26 Correct 66 ms 17800 KB Output is correct
27 Correct 80 ms 16696 KB Output is correct
28 Correct 30 ms 9920 KB Output is correct
29 Correct 59 ms 14592 KB Output is correct
30 Correct 57 ms 14748 KB Output is correct
31 Correct 57 ms 15040 KB Output is correct
32 Correct 60 ms 17312 KB Output is correct