oj.uz

Submission #986272

# Submission time Handle Problem Language Result Execution time Memory
986272 2024-05-20T07:48:03 Z Do_you_copy One-Way Streets (CEOI17_oneway) C++17
100 / 100
 73 ms 28468 KB 
#include <bits/stdc++.h>
//#define int long long
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ull = unsigned ll;
using ld = long double;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());
    
ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}
    
ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}
    
//const ll Mod = 1000000007;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 2e5 + 1;
int n, m, k;
    
struct TDSU{
    vector <pii> save;
    vector <int> lab;
    TDSU(){}
    TDSU(int _n){
        lab.resize(_n, -1);
    }
    inline void resize(int _n){
        lab.resize(_n, -1);
    }
    inline int find_set(int u){
        if (lab[u] < 0) return u;
        return lab[u] = find_set(lab[u]);
    }
    inline int find(int u){
        if (lab[u] < 0) return u;
        return find(lab[u]);
    }
    inline void merge(int u, int v){
        if (lab[u] > lab[v]) swap(u, v);
        save.pb({v, lab[v]});
        lab[u] += lab[v];
        lab[v] = u;
    }
    inline void undo(){
    
        int v = save.back().fi;
        int u = lab[v];
        lab[v] = save.back().se;
        lab[u] -= lab[v];
        save.pop_back();
    }
    inline void clear(){
        lab.clear();
        save.clear();
    }
    inline void reset(int _n){
        clear();
        resize(_n);
    }
    inline void roll_back(int _n){
        while (save.size() > _n) undo();
    }
};
TDSU dsu;
int timedfs, low[maxN], num[maxN];
int id[maxN];
int mark[maxN];
int node_cnt;
    
struct TEdge{
    int u, v, idx;
};
TEdge e[maxN];
vector <TEdge> adj[maxN];
    
void dfs(int u, int idx){
    low[u] = num[u] = ++timedfs;
    for (auto i: adj[u]){
        int v = i.u ^ i.v ^ u;
        if (i.idx == idx) continue;
        if (!num[v]){
            dfs(v, i.idx);
            low[u] = min(low[u], low[v]);
            if (low[v] == num[v]) mark[i.idx] = 1;
        }
        else{
            low[u] = min(low[u], num[v]);
        }
    }
}
    
vector <int> adj1[maxN];
int depth[maxN];
int val[maxN];
    
void dfs1(int u, int p){
    depth[u] = depth[p] + 1;
    for (auto i: adj1[u]){
        if (i == p) continue;
        dfs1(i, u);
        val[u] += val[i];
    }
}
    
void Init(){
    cin >> n >> m;
    for (int i = 1; i <= m; ++i){
        cin >> e[i].u >> e[i].v;
        e[i].idx = i;
        adj[e[i].u].pb(e[i]);
        adj[e[i].v].pb(e[i]);
    }
    for (int i = 1; i <= n; ++i){
        if (!num[i]) dfs(i, 0);
    }
    dsu.resize(n + 1);
    vector <int> bridge;
    for (int i = 1; i <= m; ++i){
        if (!mark[i]){
            int x = dsu.find_set(e[i].u);
            int y = dsu.find_set(e[i].v);
            if (x != y){
                dsu.merge(x, y);
            }
        }
        else bridge.pb(i);
    }
    for (int i = 1; i <= n; ++i){
        int j = dsu.find_set(i);
        if (!id[j]) id[j] = ++node_cnt;
        id[i] = id[j];
    }
    for (int i: bridge){
        int u = id[e[i].u];
        int v = id[e[i].v];
        adj1[u].pb(v);
        adj1[v].pb(u);
    }
    cin >> k;
    for (int i = 1; i <= k; ++i){
        int u, v;
        cin >> u >> v;
        u = id[u];
        v = id[v];
        ++val[u];
        --val[v];
    }
    for (int i = 1; i <= node_cnt; ++i){
        if (!depth[i]){
            dfs1(i, 0);
        }
    }
    for (int i = 1; i <= m; ++i){
        int x = id[e[i].u];
        int y = id[e[i].v];
        if (x == y) cout << "B";
        if(depth[x]>depth[y]){
            if(!val[x]) cout<<"B";
            if(val[x] > 0) cout<<"R";
            if(val[x] < 0) cout<<"L";
        }
        if(depth[x] < depth[y]){
            if(!val[y]) cout<<"B";
            if(val[y] > 0) cout<<"L";
            if(val[y] < 0) cout<<"R";
        }
    }
}
    
#define debu
#define taskname "test"
signed main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        #ifdef debug
        freopen(taskname".out", "w", stdout);
        #endif
    }
    faster;
    ll tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
    if (fopen("timeout.txt", "r")){
        ofstream timeout("timeout.txt");
        timeout << 1000 * double(clock()) / CLOCKS_PER_SEC;
        #ifndef debug
        cerr << "\nTime elapsed: " << 1000 * double(clock()) / CLOCKS_PER_SEC << "ms\n";
        #endif
    }
}

Compilation message

oneway.cpp: In member function 'void TDSU::roll_back(int)':
oneway.cpp:72:28: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   72 |         while (save.size() > _n) undo();
      |                ~~~~~~~~~~~~^~~~
oneway.cpp: In function 'int main()':
oneway.cpp:185:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 3 ms 14780 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 3 ms 12636 KB Output is correct
7 Correct 3 ms 14964 KB Output is correct
8 Correct 3 ms 14684 KB Output is correct
9 Correct 3 ms 14680 KB Output is correct
10 Correct 3 ms 14684 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 3 ms 14780 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 3 ms 12636 KB Output is correct
7 Correct 3 ms 14964 KB Output is correct
8 Correct 3 ms 14684 KB Output is correct
9 Correct 3 ms 14680 KB Output is correct
10 Correct 3 ms 14684 KB Output is correct
11 Correct 30 ms 20520 KB Output is correct
12 Correct 35 ms 21456 KB Output is correct
13 Correct 37 ms 22492 KB Output is correct
14 Correct 43 ms 23312 KB Output is correct
15 Correct 46 ms 23824 KB Output is correct
16 Correct 50 ms 24132 KB Output is correct
17 Correct 54 ms 25268 KB Output is correct
18 Correct 55 ms 24016 KB Output is correct
19 Correct 51 ms 26380 KB Output is correct
20 Correct 32 ms 20960 KB Output is correct
21 Correct 31 ms 20472 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 3 ms 14780 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 3 ms 12636 KB Output is correct
7 Correct 3 ms 14964 KB Output is correct
8 Correct 3 ms 14684 KB Output is correct
9 Correct 3 ms 14680 KB Output is correct
10 Correct 3 ms 14684 KB Output is correct
11 Correct 30 ms 20520 KB Output is correct
12 Correct 35 ms 21456 KB Output is correct
13 Correct 37 ms 22492 KB Output is correct
14 Correct 43 ms 23312 KB Output is correct
15 Correct 46 ms 23824 KB Output is correct
16 Correct 50 ms 24132 KB Output is correct
17 Correct 54 ms 25268 KB Output is correct
18 Correct 55 ms 24016 KB Output is correct
19 Correct 51 ms 26380 KB Output is correct
20 Correct 32 ms 20960 KB Output is correct
21 Correct 31 ms 20472 KB Output is correct
22 Correct 63 ms 25272 KB Output is correct
23 Correct 67 ms 23756 KB Output is correct
24 Correct 65 ms 24012 KB Output is correct
25 Correct 73 ms 28468 KB Output is correct
26 Correct 71 ms 25040 KB Output is correct
27 Correct 64 ms 24032 KB Output is correct
28 Correct 26 ms 15960 KB Output is correct
29 Correct 43 ms 20444 KB Output is correct
30 Correct 45 ms 20692 KB Output is correct
31 Correct 45 ms 20952 KB Output is correct
32 Correct 52 ms 23500 KB Output is correct