oj.uz

답안 #425915

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
425915 2021-06-13T12:20:16 Z oleh1421 One-Way Streets (CEOI17_oneway) C++17
60 / 100
 3000 ms 27200 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];

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;
        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 ind=cur.second;
        if (to==pr) continue;
        dfs3(to,v,ind);
        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<=k;i++){
        for (int j=1;j<=n;j++) used[j]=false;

        dfs4(x[i]);
        int cur=y[i];
        while (cur!=x[i]){
            int to=p[cur].first;
            int ind=p[cur].second;
            if (comp[a[ind]]==to) {
                if (ans[ind]=='L') exit(1);
                ans[ind]='R';

            }
            else {
                if (ans[ind]=='R') exit(1);

                ans[ind]='L';
            }
            cur=to;
        }
    }
    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++){
//        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;
}

Compilation message

oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:57:13: warning: unused variable 'ind' [-Wunused-variable]
   57 |         int ind=cur.second;
      |             ^~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 4 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 7 ms 5196 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 7 ms 5196 KB Output is correct
8 Correct 6 ms 5196 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 5 ms 5068 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 4 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 7 ms 5196 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 7 ms 5196 KB Output is correct
8 Correct 6 ms 5196 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 5 ms 5068 KB Output is correct
11 Correct 50 ms 10172 KB Output is correct
12 Correct 61 ms 11160 KB Output is correct
13 Correct 99 ms 12684 KB Output is correct
14 Correct 152 ms 16220 KB Output is correct
15 Correct 148 ms 17712 KB Output is correct
16 Correct 168 ms 24604 KB Output is correct
17 Correct 1637 ms 26112 KB Output is correct
18 Correct 1084 ms 24620 KB Output is correct
19 Correct 1440 ms 27200 KB Output is correct
20 Correct 59 ms 10732 KB Output is correct
21 Correct 58 ms 10564 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 4 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 7 ms 5196 KB Output is correct
6 Correct 4 ms 5068 KB Output is correct
7 Correct 7 ms 5196 KB Output is correct
8 Correct 6 ms 5196 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 5 ms 5068 KB Output is correct
11 Correct 50 ms 10172 KB Output is correct
12 Correct 61 ms 11160 KB Output is correct
13 Correct 99 ms 12684 KB Output is correct
14 Correct 152 ms 16220 KB Output is correct
15 Correct 148 ms 17712 KB Output is correct
16 Correct 168 ms 24604 KB Output is correct
17 Correct 1637 ms 26112 KB Output is correct
18 Correct 1084 ms 24620 KB Output is correct
19 Correct 1440 ms 27200 KB Output is correct
20 Correct 59 ms 10732 KB Output is correct
21 Correct 58 ms 10564 KB Output is correct
22 Execution timed out 3091 ms 17812 KB Time limit exceeded
23 Halted 0 ms 0 KB -