oj.uz

Submission #563696

# Submission time Handle Problem Language Result Execution time Memory
563696 2022-05-18T02:38:49 Z hohohaha One-Way Streets (CEOI17_oneway) C++14
100 / 100
 217 ms 46312 KB 
#include<bits/stdc++.h>
using namespace std;

#define fori(i, l, r) for(int i = (int) (l); i <= (int) (r); i++) 
#define ford(i, r, l) for(int i = (int) (r); i >= (int) (l); i--) 
#define ii pair<int, int> 
#define fi first
#define se second
#define vi vector<int> 
#define eb emplace_back
#define em emplace
#define sp ' '
#define endl '\n'
//#define int long long

#define ld long double

const int maxn = 2e5 + 5; 

int n, m;
vector<pair<int, ii> > g[maxn]; ii E[maxn]; 
int tin[maxn]; 
int tinpt; 
int low[maxn]; 
bool bridge[maxn];

stack<int> st; 
int cc[maxn]; 

int q; 
int x[maxn]; 
int y[maxn]; 

vector<pair<int, ii> > g2[maxn]; 
int tout[maxn]; 
int dep[maxn]; 
int par[maxn][20]; 
int parid[maxn]; 
int pardir[maxn]; 
int dir[maxn][20];

int ans[maxn]; 

void dfs_prep(int u, int pid) { 
	tin[u] = low[u] = ++tinpt; 
	st.push(u); 
	
	for(auto e: g[u]) { 
		int v = e.fi, id = e.se.fi, dir = e.se.se; 
		if(id == pid) continue; 
		if(!tin[v]) { 
			dfs_prep(v, id);
			low[u] = min(low[u], low[v]);  
		}
		else if(tin[v] < tin[u]) { 
			low[u] = min(low[u], tin[v]); 
		}
	}
	if(low[u] >= tin[u]) { 
		while(1) { 
			int top = st.top(); 
			cc[top] = u; 
			st.pop(); 
			if(top == u) break; 
		}
		if(pid >= 0) bridge[pid] = 1; 
	}
}

void dfs_prep_2(int u, int p) { 
    tin[u] = ++tinpt; 
    
    fori(bit, 1, 19) { 
        par[u][bit] = par[par[u][bit - 1]][bit - 1]; 
    }
    for(auto e: g2[u]) { 
        int v = e.fi, id = e.se.fi, dir = e.se.se; 
        if(v - p) { 
            dep[v] = dep[u] + 1; 
            par[v][0] = u; 
            parid[v] = id; 
            pardir[v] = dir ^ 1; 
            dfs_prep_2(v, u);
        }
    }
    tout[u] = tinpt; 
}

bool isan(int u, int v) { 
    return tin[u] <= tin[v] and tout[v] <= tout[u]; 
}

void jump(int u, int v, int dir) { 
    if(isan(u, v)) return; 
    
    //cout << "jump " << u << v << endl; 
    
    ford(bit, 19, 0) { 
        if(isan(par[u][bit], v)) continue; 
        ::dir[u][bit] = dir;
        u = par[u][bit];
    }
    ::dir[u][0] = dir; 
    // cout << "lca: " << par[u][0] << endl; 
}

signed main() { 
//	freopen("oneway.inp", "r", stdin); 
//	freopen("oneway.out", "w", stdout); 
	ios_base::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0); 
	
	cin >> n >> m; 
	fori(i, 1, m) {
		int u, v;
		cin >> u >> v;  
		E[i] = ii(u, v); 
		g[u].eb(make_pair(v, ii(i, 0)));
		g[v].eb(make_pair(u, ii(i, 1))); 
	}
	
	fori(i, 1, n) if(!tin[i]) dfs_prep(i, -1); 
	
	//fori(i, 1, n) cout << cc[i] << endl; 
	
	fori(i, 1, m) if(bridge[i]) g2[cc[E[i].fi]].eb(make_pair(cc[E[i].se], ii(i, 0))), g2[cc[E[i].se]].eb(make_pair(cc[E[i].fi], ii(i, 1)));
//	
	tinpt = 0; 
	fill(tin + 1, tin + n + 1, 0ll); 
    fori(i, 1, n) if(!tin[i]) { 
        par[i][0] = i; 
        dfs_prep_2(i, i);
    }
    
    cin >> q; 
	fori(i, 1, q) { 
		cin >> x[i] >> y[i];
		if(cc[x[i]] == cc[y[i]]) continue;
		jump(cc[x[i]], cc[y[i]], 1); 
		jump(cc[y[i]], cc[x[i]], 2); 
	}
	ford(bit, 19, 1) { 
	   fori(i, 1, n) { 
	       if(dir[i][bit]) { 
	           dir[i][bit - 1] = dir[i][bit]; 
	           dir[par[i][bit - 1]][bit - 1] = dir[i][bit]; 
	       }
	   }
	}
	fori(i, 1, n) { 
	   if(par[i][0] != i and dir[i][0]) ans[parid[i]] = (pardir[i] ^ dir[i][0] - 1) + 1; 
	}
	fori(i, 1, m) { 
	       if(ans[i] == 1) cout << "R";
	       else if(ans[i] == 2) cout << "L";
	       else cout << "B";
	}
}

Compilation message

oneway.cpp: In function 'void dfs_prep(int, int)':
oneway.cpp:49:31: warning: unused variable 'dir' [-Wunused-variable]
   49 |   int v = e.fi, id = e.se.fi, dir = e.se.se;
      |                               ^~~
oneway.cpp: In function 'int main()':
oneway.cpp:152:77: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
  152 |     if(par[i][0] != i and dir[i][0]) ans[parid[i]] = (pardir[i] ^ dir[i][0] - 1) + 1;
      |                                                                   ~~~~~~~~~~^~~

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9792 KB Output is correct
3 Correct 5 ms 9940 KB Output is correct
4 Correct 6 ms 9996 KB Output is correct
5 Correct 6 ms 9996 KB Output is correct
6 Correct 6 ms 9884 KB Output is correct
7 Correct 6 ms 10068 KB Output is correct
8 Correct 7 ms 10008 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 5 ms 9864 KB Output is correct
11 Correct 41 ms 18764 KB Output is correct
12 Correct 50 ms 21320 KB Output is correct
13 Correct 62 ms 24384 KB Output is correct
14 Correct 72 ms 28364 KB Output is correct
15 Correct 77 ms 29696 KB Output is correct
16 Correct 102 ms 31228 KB Output is correct
17 Correct 115 ms 40628 KB Output is correct
18 Correct 100 ms 34876 KB Output is correct
19 Correct 109 ms 42056 KB Output is correct
20 Correct 55 ms 21824 KB Output is correct
21 Correct 49 ms 24876 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 5 ms 9792 KB Output is correct
3 Correct 5 ms 9940 KB Output is correct
4 Correct 6 ms 9996 KB Output is correct
5 Correct 6 ms 9996 KB Output is correct
6 Correct 6 ms 9884 KB Output is correct
7 Correct 6 ms 10068 KB Output is correct
8 Correct 7 ms 10008 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 5 ms 9864 KB Output is correct
11 Correct 41 ms 18764 KB Output is correct
12 Correct 50 ms 21320 KB Output is correct
13 Correct 62 ms 24384 KB Output is correct
14 Correct 72 ms 28364 KB Output is correct
15 Correct 77 ms 29696 KB Output is correct
16 Correct 102 ms 31228 KB Output is correct
17 Correct 115 ms 40628 KB Output is correct
18 Correct 100 ms 34876 KB Output is correct
19 Correct 109 ms 42056 KB Output is correct
20 Correct 55 ms 21824 KB Output is correct
21 Correct 49 ms 24876 KB Output is correct
22 Correct 215 ms 42636 KB Output is correct
23 Correct 175 ms 40876 KB Output is correct
24 Correct 159 ms 41176 KB Output is correct
25 Correct 217 ms 46312 KB Output is correct
26 Correct 200 ms 42096 KB Output is correct
27 Correct 174 ms 40908 KB Output is correct
28 Correct 33 ms 15692 KB Output is correct
29 Correct 69 ms 23340 KB Output is correct
30 Correct 73 ms 24508 KB Output is correct
31 Correct 67 ms 23804 KB Output is correct
32 Correct 133 ms 33900 KB Output is correct