oj.uz

Submission #1005689

# Submission time Handle Problem Language Result Execution time Memory
1005689 2024-06-22T18:55:03 Z Rifal One-Way Streets (CEOI17_oneway) C++14
60 / 100
 3000 ms 34916 KB 
#include <bits/stdc++.h>
#include <fstream>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define mod 1000000007
#define INF 1000000000
#define INF2 2000000000
#define fi first
#define se second
using namespace std;
double const EPS = 1e-14;
const int P = 1007;
typedef long long ll;
using namespace __gnu_pbds;
typedef long long ll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // find_by_order, order_of_key
const int Max = 1e5 + 5;
vector<int> v[Max];
int sta[Max], low[Max], par[Max];
int tim = 0, nod = 0;
map<pair<int,int>,int> mp, check;
bool vis[Max], ok = false;
void dfs(int s, int p) {
    tim++;
    vis[s] = 1;
    sta[s] = tim;
    low[s] = tim;
    for(auto i : v[s]) {
        if(vis[i] == 0) {
            dfs(i,s);
            low[s] = min(low[s],low[i]);
            if(low[i] > sta[s]) {
              //  cout << s << ' ' << i << ' ' << "bb" << endl;
                check[{i,s}] = 1;
                check[{s,i}] = 1;
            }
        }
        else if(i != p || par[s] > 0){
            low[s] = min(sta[i],low[s]);
        }
        else if(i == p) {
            par[s]++;
        }
        
    }
}
void dfs2(int s) {
    vis[s] = 1;
    if(s == nod) {
        ok = true; return;
    }
    for(auto i : v[s]) {
        if(vis[i] == 0 && ok == false) {
            dfs2(i);
            if(ok) {
                if(check[{s,i}] == 1) {
                    mp[{s,i}] = 2;
                    mp[{i,s}] = 3;
                }
            }
        }
    }

}
int main()
{
    ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
    int n, m; cin >> n >> m;
    pair<int,int> edge[m];
    for(int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        edge[i].fi = a, edge[i].se = b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i = 1; i <= n; i++) {
        if(vis[i] == 0) {
            dfs(i,0);
        }
    }
    int p; cin >> p;
    while(p--) {
        int a, b; cin >> a >> b;
        nod = b; ok = false;
        for(int i = 1; i <= n; i++) vis[i] = 0;
        dfs2(a);
    }
    for(int i = 0; i < m; i++) {
        if(mp[{edge[i].fi,edge[i].se}] == 0) cout << 'B';
        else if(mp[{edge[i].fi,edge[i].se}] == 3) cout << 'L';
        else cout << 'R';
    }
    cout << endl;
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3676 KB Output is correct
2 Correct 1 ms 3676 KB Output is correct
3 Correct 1 ms 3932 KB Output is correct
4 Correct 2 ms 3932 KB Output is correct
5 Correct 4 ms 4188 KB Output is correct
6 Correct 2 ms 4020 KB Output is correct
7 Correct 4 ms 4024 KB Output is correct
8 Correct 2 ms 3932 KB Output is correct
9 Correct 3 ms 3932 KB Output is correct
10 Correct 3 ms 3932 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3676 KB Output is correct
2 Correct 1 ms 3676 KB Output is correct
3 Correct 1 ms 3932 KB Output is correct
4 Correct 2 ms 3932 KB Output is correct
5 Correct 4 ms 4188 KB Output is correct
6 Correct 2 ms 4020 KB Output is correct
7 Correct 4 ms 4024 KB Output is correct
8 Correct 2 ms 3932 KB Output is correct
9 Correct 3 ms 3932 KB Output is correct
10 Correct 3 ms 3932 KB Output is correct
11 Correct 302 ms 19284 KB Output is correct
12 Correct 408 ms 21588 KB Output is correct
13 Correct 573 ms 25168 KB Output is correct
14 Correct 645 ms 27356 KB Output is correct
15 Correct 609 ms 28244 KB Output is correct
16 Correct 121 ms 27984 KB Output is correct
17 Correct 1441 ms 34648 KB Output is correct
18 Correct 211 ms 27984 KB Output is correct
19 Correct 1555 ms 34916 KB Output is correct
20 Correct 395 ms 22096 KB Output is correct
21 Correct 249 ms 16980 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3676 KB Output is correct
2 Correct 1 ms 3676 KB Output is correct
3 Correct 1 ms 3932 KB Output is correct
4 Correct 2 ms 3932 KB Output is correct
5 Correct 4 ms 4188 KB Output is correct
6 Correct 2 ms 4020 KB Output is correct
7 Correct 4 ms 4024 KB Output is correct
8 Correct 2 ms 3932 KB Output is correct
9 Correct 3 ms 3932 KB Output is correct
10 Correct 3 ms 3932 KB Output is correct
11 Correct 302 ms 19284 KB Output is correct
12 Correct 408 ms 21588 KB Output is correct
13 Correct 573 ms 25168 KB Output is correct
14 Correct 645 ms 27356 KB Output is correct
15 Correct 609 ms 28244 KB Output is correct
16 Correct 121 ms 27984 KB Output is correct
17 Correct 1441 ms 34648 KB Output is correct
18 Correct 211 ms 27984 KB Output is correct
19 Correct 1555 ms 34916 KB Output is correct
20 Correct 395 ms 22096 KB Output is correct
21 Correct 249 ms 16980 KB Output is correct
22 Execution timed out 3009 ms 31224 KB Time limit exceeded
23 Halted 0 ms 0 KB -