oj.uz

Submission #425942

# Submission time Handle Problem Language Result Execution time Memory
425942 2021-06-13T12:29:23 Z oleh1421 One-Way Streets (CEOI17_oneway) C++17
60 / 100
 3000 ms 25932 KB 
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=100010;
const ll mod=1000000007;
const ll inf=1e15;
int a[N],b[N];
int x[N],y[N];
vector<pair<int,int> >g[N];
int timer=0;
int tin[N],tout[N],fup[N];
bool used[N];
bool imp[N];
void dfs(int v,int pr){
    used[v]=true;
    tin[v]=fup[v]=++timer;
    for (auto cur:g[v]){
        int to=cur.first;
        int ind=cur.second;
        if (ind==pr) continue;
        if (!used[to]){
            dfs(to,ind);
            if (fup[to]>tin[v]) imp[ind]=true;
            fup[v]=min(fup[v],fup[to]);
        } else {
            fup[v]=min(fup[v],tin[to]);
        }
    }
}
int comp[N];
int num=0;
void dfs1(int v){
    comp[v]=num;
    for (auto cur:g[v]){
        int to=cur.first;
        int ind=cur.second;
        if (!imp[ind] && !comp[to]){
            dfs1(to);
        }
    }
}
vector<pair<int,int> >t[N];
const int L=20;
int up[N][L];
int p_ind[N];
void dfs2(int v,int pr){
    up[v][0]=pr;
//    cout<<"0 "<<v<<" "<<pr<<endl;
    for (int i=1;i<L;i++){
        up[v][i]=up[up[v][i-1]][i-1];

    }
    used[v]=true;
    tin[v]=++timer;
    for (auto cur:t[v]){
        int to=cur.first;
        int ind=cur.second;
        if (to==pr) continue;
        p_ind[to]=ind;
        dfs2(to,v);
    }

    tout[v]=timer;
}
bool upper(int a,int b){
    return (tin[a]<=tin[b] && tout[b]<=tout[a]);
}
int lca(int a,int b){
    if (upper(a,b)) return a;
    if (upper(b,a)) return b;
    for (int i=L-1;i>=0;i--){
        if (!upper(up[a][i],b)) a=up[a][i];
    }
    return up[a][0];
}
int add[N][2];
char ans[N];
void dfs3(int v,int pr,int ind){
    used[v]=true;
    for (auto cur:t[v]){
        int to=cur.first;
        int nxt=cur.second;
        if (to==pr) continue;
        dfs3(to,v,nxt);
        add[v][0]+=add[to][0];
        add[v][1]+=add[v][1];
    }
//    if (add[v][0] && add[v][1]) exit(1);
    if (add[v][0]){
        if (comp[a[ind]]==v) ans[ind]='R';
        else ans[ind]='L';
    } else if (add[v][1]){
        if (comp[a[ind]]==v) ans[ind]='L';
        else ans[ind]='R';
    } else {

    }

}
pair<int,int> p[N];
void dfs4(int v){
    used[v]=true;
    for (auto cur:t[v]){
        int to=cur.first;
        int ind=cur.second;
        if (used[to]) continue;
        p[to]={v,ind};
        dfs4(to);
    }

}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m;cin>>n>>m;
    for (int i=1;i<=m;i++){
        cin>>a[i]>>b[i];
        g[a[i]].push_back({b[i],i});
        g[b[i]].push_back({a[i],i});
        ans[i]='B';
    }
    int k;cin>>k;
    for (int i=1;i<=k;i++){
        cin>>x[i]>>y[i];
    }
    for (int i=1;i<=n;i++){
        if (!used[i]){
            dfs(i,0);
        }
    }

    for (int i=1;i<=n;i++){
        if (!comp[i]){
            num++;
            dfs1(i);
        }
    }
    for (int v=1;v<=n;v++){
        for (auto cur:g[v]){
            int to=cur.first;
            int ind=cur.second;
            if (imp[ind]){
                t[comp[v]].push_back({comp[to],ind});
            }
        }
    }
    for (int i=1;i<=k;i++){
        x[i]=comp[x[i]];
        y[i]=comp[y[i]];
    }
    for (int i=1;i<=n;i++) used[i]=false,tin[i]=0;
    tin[0]=0;
    timer=0;
    for (int i=1;i<=num;i++){
        if (!used[i]) dfs2(i,0);
    }
    tout[0]=timer;

    for (int i=1;i<=k;i++){
        for (int j=1;j<=n;j++) used[j]=false;
        int lc=lca(x[i],y[i]);
        int cur=y[i];
        while (cur!=lc){
            int to=up[cur][0];
            int ind=p_ind[cur];
            if (comp[a[ind]]==to) {
                ans[ind]='R';

            }
            else {

                ans[ind]='L';
            }
            cur=to;
        }
        cur=x[i];
        while (cur!=lc){
            int to=up[cur][0];
            int ind=p_ind[cur];
            if (comp[a[ind]]==to) {
                ans[ind]='L';
            }
            else {

                ans[ind]='R';
            }
            cur=to;
        }
    }
//    for (int i=1;i<=k;i++){
//        int lc=lca(x[i],y[i]);
//        add[x[i]][0]++;
//        add[y[i]][1]++;
//        add[lc][0]--;
//        add[lc][1]--;
//    }
//    for (int i=1;i<=num;i++) used[i]=false;
//    for (int i=1;i<=num;i++) {
//        if (!used[i]){
//            dfs3(i,0,0);
//        }
//    }
    for (int i=1;i<=m;i++) cout<<ans[i];
    cout<<endl;
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 4 ms 5196 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 5 ms 5196 KB Output is correct
8 Correct 5 ms 5196 KB Output is correct
9 Correct 4 ms 5072 KB Output is correct
10 Correct 5 ms 5068 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 4 ms 5196 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 5 ms 5196 KB Output is correct
8 Correct 5 ms 5196 KB Output is correct
9 Correct 4 ms 5072 KB Output is correct
10 Correct 5 ms 5068 KB Output is correct
11 Correct 55 ms 10216 KB Output is correct
12 Correct 57 ms 11180 KB Output is correct
13 Correct 77 ms 12636 KB Output is correct
14 Correct 117 ms 15828 KB Output is correct
15 Correct 97 ms 17324 KB Output is correct
16 Correct 135 ms 23376 KB Output is correct
17 Correct 259 ms 24796 KB Output is correct
18 Correct 164 ms 23336 KB Output is correct
19 Correct 195 ms 25932 KB Output is correct
20 Correct 69 ms 10692 KB Output is correct
21 Correct 55 ms 10536 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 4 ms 5196 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 5 ms 5196 KB Output is correct
8 Correct 5 ms 5196 KB Output is correct
9 Correct 4 ms 5072 KB Output is correct
10 Correct 5 ms 5068 KB Output is correct
11 Correct 55 ms 10216 KB Output is correct
12 Correct 57 ms 11180 KB Output is correct
13 Correct 77 ms 12636 KB Output is correct
14 Correct 117 ms 15828 KB Output is correct
15 Correct 97 ms 17324 KB Output is correct
16 Correct 135 ms 23376 KB Output is correct
17 Correct 259 ms 24796 KB Output is correct
18 Correct 164 ms 23336 KB Output is correct
19 Correct 195 ms 25932 KB Output is correct
20 Correct 69 ms 10692 KB Output is correct
21 Correct 55 ms 10536 KB Output is correct
22 Execution timed out 3060 ms 25452 KB Time limit exceeded
23 Halted 0 ms 0 KB -