Submission #1090901

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090901		kiethm07	One-Way Streets (CEOI17_oneway)	C++11	100 / 100	97 ms	24164 KiB

oneway

#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 (stderr)

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40