oj.uz

답안 #349285

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
349285 2021-01-17T10:30:46 Z doowey One-Way Streets (CEOI17_oneway) C++14
60 / 100
 3000 ms 13244 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 10;
vector<pii> T[N];
int tin[N];
int tout[N];
int low[N];
int u[N], v[N];
bool bridge[N];
int ti;

void dfs(int u, int pp){
    ti++;
    tin[u]=ti;
    low[u]=tin[u];
    for(auto x : T[u]){
        if(tin[x.fi] == 0){
            dfs(x.fi,x.se);
            low[u]=min(low[u],low[x.fi]);
            if(tin[u] < low[x.fi]){
                bridge[x.se]=true;
            }
        }
        else if(x.se != pp){
            low[u]=min(low[u],tin[x.fi]);
        }
    }
    tout[u]=ti;
}


int las[N];
int idx[N];

void dfs(int u){
    for(auto x : T[u]){
        if(las[x.fi] == -1){
            las[x.fi]=u;
            idx[x.fi]=x.se;
            dfs(x.fi);
        }
    }
}

char sol[N];

void setd(int xi, int yi, int id){
    if(xi == u[id]){
        sol[id]='R';
    }
    else{
        sol[id]='L';
    }
}

int main(){
    fastIO;
    int n, m, p;
    cin >> n >> m;
    for(int i = 1; i <= m; i ++ ){
        cin >> u[i] >> v[i];
        T[u[i]].push_back(mp(v[i],i));
        T[v[i]].push_back(mp(u[i],i));
    }
    for(int i = 1; i <= n; i ++ ){
        if(tin[i] == 0){
            dfs(i,-1);
        }
    }
    for(int i = 1; i <= m; i ++ ){
        sol[i]='B';
    }
    cin >> p;
    int xi, yi;
    for(int i = 1; i <= p ; i ++ ){
        cin >> xi >> yi;
        for(int j = 1; j <= n; j ++ ){
            las[j]=-1;
            idx[j]=-1;
        }
        las[xi]=0;
        dfs(xi);
        while(yi != xi){
            if(bridge[idx[yi]])
                setd(las[yi],yi,idx[yi]);
            yi = las[yi];
        }
    }
    for(int i = 1; i <= m ; i ++ ){
        cout << sol[i];
    }
    cout << "\n";
    return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 3 ms 2796 KB Output is correct
4 Correct 2 ms 2796 KB Output is correct
5 Correct 4 ms 2796 KB Output is correct
6 Correct 3 ms 2796 KB Output is correct
7 Correct 4 ms 2796 KB Output is correct
8 Correct 4 ms 2796 KB Output is correct
9 Correct 3 ms 2796 KB Output is correct
10 Correct 3 ms 2796 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 3 ms 2796 KB Output is correct
4 Correct 2 ms 2796 KB Output is correct
5 Correct 4 ms 2796 KB Output is correct
6 Correct 3 ms 2796 KB Output is correct
7 Correct 4 ms 2796 KB Output is correct
8 Correct 4 ms 2796 KB Output is correct
9 Correct 3 ms 2796 KB Output is correct
10 Correct 3 ms 2796 KB Output is correct
11 Correct 188 ms 9068 KB Output is correct
12 Correct 324 ms 10220 KB Output is correct
13 Correct 557 ms 11372 KB Output is correct
14 Correct 872 ms 12256 KB Output is correct
15 Correct 921 ms 12356 KB Output is correct
16 Correct 93 ms 10604 KB Output is correct
17 Correct 732 ms 12260 KB Output is correct
18 Correct 937 ms 10604 KB Output is correct
19 Correct 547 ms 13244 KB Output is correct
20 Correct 464 ms 9844 KB Output is correct
21 Correct 331 ms 9708 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 3 ms 2796 KB Output is correct
4 Correct 2 ms 2796 KB Output is correct
5 Correct 4 ms 2796 KB Output is correct
6 Correct 3 ms 2796 KB Output is correct
7 Correct 4 ms 2796 KB Output is correct
8 Correct 4 ms 2796 KB Output is correct
9 Correct 3 ms 2796 KB Output is correct
10 Correct 3 ms 2796 KB Output is correct
11 Correct 188 ms 9068 KB Output is correct
12 Correct 324 ms 10220 KB Output is correct
13 Correct 557 ms 11372 KB Output is correct
14 Correct 872 ms 12256 KB Output is correct
15 Correct 921 ms 12356 KB Output is correct
16 Correct 93 ms 10604 KB Output is correct
17 Correct 732 ms 12260 KB Output is correct
18 Correct 937 ms 10604 KB Output is correct
19 Correct 547 ms 13244 KB Output is correct
20 Correct 464 ms 9844 KB Output is correct
21 Correct 331 ms 9708 KB Output is correct
22 Execution timed out 3083 ms 12524 KB Time limit exceeded
23 Halted 0 ms 0 KB -