oj.uz

Submission #627112

# Submission time Handle Problem Language Result Execution time Memory
627112 2022-08-12T08:03:26 Z Do_you_copy One-Way Streets (CEOI17_oneway) C++17
60 / 100
 121 ms 32316 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 <pii> adj1[maxN];
int lift[maxN][20];
int depth[maxN];
int val[maxN];

void dfs1(int u, int p){
    lift[u][0] = p;
    depth[u] = depth[p] + 1;

    for (int i = 1; i < 20; ++i){
        lift[u][i] = lift[lift[u][i - 1]][i - 1];
        if (!lift[u][i]) break;
    }
    for (auto i: adj1[u]){
        int v = i.fi;
        if (v == p) continue;
        dfs1(v, u);
    }
}

int lca(int u, int v){
    if (depth[u] < depth[v]) swap(u, v);
    int k = depth[u] - depth[v];
    while (k){
        int t = k & -k;
        u = lift[u][__lg(t)];
        k -= t;
    }
    if (u == v) return u;
    for (int i = 19; i >= 0; --i){
        if (lift[u][i] != lift[v][i]){
            u = lift[u][i];
            v = lift[v][i];
        }
    }
    return lift[u][0];
}

void dfs2(int u, int p){
    for (auto i: adj1[u]){
        int v = i.fi;
        if (v == p) continue;
        dfs2(v, u);
        val[u] += val[v];
        if (!val[v]){
            mark[abs(i.se)] = 0;
        }
        else if (val[v] * i.se < 0) mark[abs(i.se)] = 1;
        else mark[abs(i.se)] = -1;
    }
}

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);
                //cerr << e[i].u << " " << e[i].v << "?\n";
            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, i});
        adj1[v].pb({u, -i});
    }
    for (int i = 1; i <= node_cnt; ++i){
        if (!lift[i][0]){
            dfs1(i, 0);
        }
    }
    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 (!lift[i][0]){
            dfs2(i, 0);
        }
    }
    for (int i = 1; i <= m; ++i){
        if (!mark[i]) cout << 'B';
        else if (mark[i] < 0) cout << 'L';
        else 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:220:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  220 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 7 ms 9940 KB Output is correct
5 Correct 5 ms 9940 KB Output is correct
6 Correct 7 ms 9812 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Correct 5 ms 9940 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 6 ms 9812 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 7 ms 9940 KB Output is correct
5 Correct 5 ms 9940 KB Output is correct
6 Correct 7 ms 9812 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Correct 5 ms 9940 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 6 ms 9812 KB Output is correct
11 Correct 47 ms 16632 KB Output is correct
12 Correct 46 ms 18064 KB Output is correct
13 Correct 48 ms 19504 KB Output is correct
14 Correct 97 ms 22532 KB Output is correct
15 Correct 92 ms 24008 KB Output is correct
16 Correct 84 ms 29876 KB Output is correct
17 Correct 91 ms 31160 KB Output is correct
18 Correct 105 ms 29904 KB Output is correct
19 Correct 105 ms 32316 KB Output is correct
20 Correct 46 ms 17232 KB Output is correct
21 Correct 42 ms 17376 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9812 KB Output is correct
4 Correct 7 ms 9940 KB Output is correct
5 Correct 5 ms 9940 KB Output is correct
6 Correct 7 ms 9812 KB Output is correct
7 Correct 5 ms 9940 KB Output is correct
8 Correct 5 ms 9940 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 6 ms 9812 KB Output is correct
11 Correct 47 ms 16632 KB Output is correct
12 Correct 46 ms 18064 KB Output is correct
13 Correct 48 ms 19504 KB Output is correct
14 Correct 97 ms 22532 KB Output is correct
15 Correct 92 ms 24008 KB Output is correct
16 Correct 84 ms 29876 KB Output is correct
17 Correct 91 ms 31160 KB Output is correct
18 Correct 105 ms 29904 KB Output is correct
19 Correct 105 ms 32316 KB Output is correct
20 Correct 46 ms 17232 KB Output is correct
21 Correct 42 ms 17376 KB Output is correct
22 Incorrect 121 ms 31180 KB Output isn't correct
23 Halted 0 ms 0 KB -