oj.uz

Submission #1086556

# Submission time Handle Problem Language Result Execution time Memory
1086556 2024-09-11T03:22:41 Z KawakiMeido One-Way Streets (CEOI17_oneway) C++17
0 / 100
 3 ms 4956 KB 
/*Author: KawakiMeido*/
#include <bits/stdc++.h>
#define pb push_back
#define endl "\n"
#define ll long long
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define piii pair<pii,int>
#define fi first
#define se second

using namespace std;

/*Constants*/
const int N = 2e5+10;
const int INF = 1e9+7;
const long long LLINF = 1e18+3;

/*TestCases*/
int test=1;
void solve();
void TestCases(bool v){
    if (v) cin >> test;
    while(test--) solve();
}

/*Global Variables*/
int n,m,timedfs=0,q;
vector<piii> adj[N];
int num[N],low[N];
int dir[N];
int pre[N];
bool IsBridge[N];

//DSU
//void Init(){
//    for (int i=1; i<=n; i++){
//        parent[i] = i;
//    }
//}
//
//int Find(int x){
//    return (x == parent[x])? x : parent[x] = Find(parent[x]);
//}
//
//void Union(int u, int v){
//    int x = Find(u);
//    int y = Find(v);
//    if (x!=y){
//        parent[y] = x;
//    }
//}

int DFS(int u, int prev){
    int t = 0;
    num[u] = low[u] = ++timedfs;
    for (auto in:adj[u]){
        int v = in.fi.fi;
        int id = in.fi.se;
        int dr = in.se;

        if (id == prev) continue;
        if (!num[v]){
            int tmp = DFS(v,id);
            t+=tmp;
//            cout << u << " " << v << " " << tmp << endl;
            low[u] = min(low[u],low[v]);
            if (num[v] == low[v]){
//                Union(u,v);
                IsBridge[id] = true;
                if (tmp!= 0){
                    dir[id] = dr;
                    if (tmp<0) dir[id] = -dir[id];
                }
//                adj2[Find(u)].push_back(Find(v));
//                adj2[Find(v)].push_back(Find(u));
            }
        }
        else low[u] = min(low[u],num[v]);
    }
    t+=pre[u];
    return t;
}

/*Solution*/
void solve(){
    cin >> n >> m;
//    Init();
    for (int i=1; i<=m; i++){
        int u,v; cin >> u >> v;
        adj[u].push_back({{v,i},1});
        adj[v].push_back({{u,i},-1});
    }
    cin >> q;
    for (int i=1; i<=q; i++){
        int u,v; cin >> u >> v;
        pre[u]--;
        pre[v]++;
    }
    DFS(1,0);
    for (int i=1; i<=m; i++){
        if (dir[i] == 0) cout << "B";
        else if (dir[i] == 1) cout << "R";
        else cout << "L";
    }
//    cout << endl;
//    for (int i=1; i<=n; i++){
//        cout << low[i] << " ";
//    }
//    cout << endl;
}

/*Driver Code*/
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    TestCases(0);

    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -