oj.uz

Submission #1090901

# Submission time Handle Problem Language Result Execution time Memory
1090901 2024-09-19T05:56:07 Z kiethm07 One-Way Streets (CEOI17_oneway) C++11
100 / 100
 97 ms 24164 KB 
#include <bits/stdc++.h>
 
#define pii pair<int,int>
#define fi first
#define se second
 
using namespace std;
 
const int N = 1e5 + 5;
 
vector<pii> a[N];
vector<pii> t[N];
int n,m,q;
int low[N], num[N];
int component[N];
bool bridge[N];
bool inv[N];
int pa[N], sz[N], head[N], pos[N], d_hld[N], id;
int val[N];
int ans[N];
int cnt = 0;
 
struct edge{
    int u,v;
    edge(){}
};
 
edge e[N];
 
void dfs1(int u,int pre){
    low[u] = num[u] = ++cnt;
    for (int i = 0; i < a[u].size(); i++){
        int v = a[u][i].fi;
        int id = a[u][i].se;
        if (id == pre) continue;
        if (num[v] != 0){
            low[u] = min(low[u], num[v]);
        }
        else{
            dfs1(v,id);
            low[u] = min(low[u], low[v]); 
            bridge[id] = low[v] == num[v];
        }
    }
}
 
void build(int u,int c){
    component[u] = c;
    for (int i = 0; i < a[u].size(); i++){
        int v = a[u][i].fi;
        int id = a[u][i].se;
        if (bridge[id]) continue;
        if (component[v] != 0) continue;
        build(v,c);
    }
}
 
void dfs2(int u,int p){
    sz[u] = 1;
    for (int i = 0; i < t[u].size(); i++){
        int v = t[u][i].fi;
        int id = t[u][i].se;
        if (v == p) continue;
        inv[id] = u != component[e[id].u];
        pa[v] = u;
        dfs2(v,u);
        sz[u] += sz[v];
    }
}
 
void hld(int u,int p){
    pos[u] = ++id;
    int cur = 0;
    int nxt = -1;
    for (int i = 0; i < t[u].size(); i++){
        int v = t[u][i].fi;
        if (v == p) continue;
        if (sz[v] > cur){
            cur = sz[v];
            nxt = v;
        }
    }
    if (nxt != -1){
        head[nxt] = head[u];
        d_hld[nxt] = d_hld[u];
        hld(nxt,u);
        for (int i = 0; i < t[u].size(); i++){
            int v = t[u][i].fi;
            if (v == p || v == nxt) continue;
            head[v] = v;
            d_hld[v] = d_hld[u] + 1;
            hld(v,u);
        }
    }
}
 
int lca(int u,int v){
    if (d_hld[u] < d_hld[v]) swap(u,v);
    while(d_hld[u] > d_hld[v]) u = pa[head[u]];
    while(head[u] != head[v]){
        u = pa[head[u]];
        v = pa[head[v]];
    }
    if (pos[u] > pos[v]) swap(u,v);
    return u;
}
 
void dfs3(int u,int p){
    for (int i = 0; i < t[u].size(); i++){
        int v = t[u][i].fi;
        int id = t[u][i].se;
        if (v == p) continue;
        dfs3(v,u);
        if (val[v] < 0) ans[id] = -1;
        else if (val[v] > 0) ans[id] = 1;
        val[u] += val[v];
    }
}
 
int main(){
    cin.tie(0) -> sync_with_stdio(0);
    #define repdimahuhu "Phanluong"
    if (fopen(repdimahuhu".inp","r")){
        freopen(repdimahuhu".inp","r",stdin);
        freopen(repdimahuhu".out","w",stdout);
    }
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        int u,v;
        cin >> u >> v;
        a[u].push_back(pii(v,i));
        a[v].push_back(pii(u,i));
        e[i].u = u;
        e[i].v = v;
    }
    for (int i = 1; i <= n; i++){
        if (num[i] == 0) dfs1(i,-1);
    }
    cnt = 0;
    for (int i = 1; i <= n; i++){
        if (component[i] != 0) continue;
        build(i,++cnt);
    }
    for (int i = 1; i <= m; i++){
        int u = component[e[i].u];
        int v = component[e[i].v];
        if (u == v) continue;
        t[u].push_back(pii(v,i));
        t[v].push_back(pii(u,i));
    }
    for (int i = 1; i <= cnt; i++){
        if (pa[i] != 0) continue;
        pa[i] = -1;
        dfs2(i,-1);
        head[i] = i;
        hld(i,-1);
    }
    cin >> q;
    while(q--){
        int u,v;
        cin >> u >> v;
        u = component[u];
        v = component[v];
        val[u] += 1;
        val[v] -= 1;
    }
    for (int i = 1; i <= cnt; i++){
        if (pa[i] != -1) continue;
        dfs3(i,-1);
    }
//    for (int i = 1; i <= m; i++){
//        int u = e[i].u;
//        int v = e[i].v;
//        cout << u << " " << v << " " << inv[i] << "\n";
//    }
    for (int i = 1; i <= m; i++){
        if (inv[i]) ans[i] *= -1;
        if (ans[i] == 0) cout << "B";
        if (ans[i] == -1) cout << "R";
        if (ans[i] == 1) cout << "L";
    }
    return 0;
}

Compilation message

oneway.cpp: In function 'void dfs1(int, int)':
oneway.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0; i < a[u].size(); i++){
      |                     ~~^~~~~~~~~~~~~
oneway.cpp: In function 'void build(int, int)':
oneway.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (int i = 0; i < a[u].size(); i++){
      |                     ~~^~~~~~~~~~~~~
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:60:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for (int i = 0; i < t[u].size(); i++){
      |                     ~~^~~~~~~~~~~~~
oneway.cpp: In function 'void hld(int, int)':
oneway.cpp:75:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for (int i = 0; i < t[u].size(); i++){
      |                     ~~^~~~~~~~~~~~~
oneway.cpp:87:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for (int i = 0; i < t[u].size(); i++){
      |                         ~~^~~~~~~~~~~~~
oneway.cpp: In function 'void dfs3(int, int)':
oneway.cpp:109:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for (int i = 0; i < t[u].size(); i++){
      |                     ~~^~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         freopen(repdimahuhu".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen(repdimahuhu".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 5260 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 3 ms 5208 KB Output is correct
7 Correct 2 ms 5164 KB Output is correct
8 Correct 3 ms 5240 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 5260 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 3 ms 5208 KB Output is correct
7 Correct 2 ms 5164 KB Output is correct
8 Correct 3 ms 5240 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct
11 Correct 26 ms 11356 KB Output is correct
12 Correct 30 ms 12628 KB Output is correct
13 Correct 33 ms 13804 KB Output is correct
14 Correct 47 ms 15700 KB Output is correct
15 Correct 45 ms 16236 KB Output is correct
16 Correct 58 ms 18776 KB Output is correct
17 Correct 50 ms 20052 KB Output is correct
18 Correct 51 ms 18764 KB Output is correct
19 Correct 52 ms 21076 KB Output is correct
20 Correct 29 ms 11932 KB Output is correct
21 Correct 26 ms 12116 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 5260 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 3 ms 5212 KB Output is correct
6 Correct 3 ms 5208 KB Output is correct
7 Correct 2 ms 5164 KB Output is correct
8 Correct 3 ms 5240 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 2 ms 5212 KB Output is correct
11 Correct 26 ms 11356 KB Output is correct
12 Correct 30 ms 12628 KB Output is correct
13 Correct 33 ms 13804 KB Output is correct
14 Correct 47 ms 15700 KB Output is correct
15 Correct 45 ms 16236 KB Output is correct
16 Correct 58 ms 18776 KB Output is correct
17 Correct 50 ms 20052 KB Output is correct
18 Correct 51 ms 18764 KB Output is correct
19 Correct 52 ms 21076 KB Output is correct
20 Correct 29 ms 11932 KB Output is correct
21 Correct 26 ms 12116 KB Output is correct
22 Correct 60 ms 21032 KB Output is correct
23 Correct 63 ms 19640 KB Output is correct
24 Correct 65 ms 19776 KB Output is correct
25 Correct 62 ms 24164 KB Output is correct
26 Correct 61 ms 20824 KB Output is correct
27 Correct 97 ms 19804 KB Output is correct
28 Correct 20 ms 9272 KB Output is correct
29 Correct 44 ms 12628 KB Output is correct
30 Correct 42 ms 12944 KB Output is correct
31 Correct 39 ms 13092 KB Output is correct
32 Correct 50 ms 17008 KB Output is correct