제출 #468125

#제출 시각아이디문제언어결과실행 시간메모리
468125Vladth11One-Way Streets (CEOI17_oneway)C++14
100 / 100
235 ms26552 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define debug(x) cerr << #x << " " << x << "\n" #define debugs(x) cerr << #x << " " << x << " " #pragma GCC optimize("Ofast,unroll-loops") using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef pair <int, int> pii; typedef pair <long double, pii> muchie; typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST; const ll NMAX = 100001; const ll INF = (1LL << 60); const ll HALF = (1LL << 59); const ll MOD = 30013; const ll BLOCK = 318; const ll base = 31; const ll nr_of_bits = 21; int n, m; int lvl[NMAX]; int dp[NMAX]; int viz[NMAX]; int cnt; int dest[NMAX]; int sursa[NMAX]; int surse[NMAX]; int deste[NMAX]; int comp[NMAX]; int parent[NMAX]; int bl[NMAX][nr_of_bits + 1]; vector <int> v[NMAX]; int stamp; pii timp[NMAX]; bool par(int a, int b){ return timp[a].first <= timp[b].first && timp[b].second <= timp[a].second; } void DFS(int node, int p){ lvl[node] = lvl[p] + 1; parent[node] = p; for(auto x : v[node]){ if(!lvl[x]){ DFS(x, node); dp[node] += dp[x]; }else if(lvl[x] > lvl[node]){ dp[node]--; }else{ dp[node]++; } } if(lvl[node] != 1) dp[node]--; } void assignComp(int node, int p){ if(!dp[node]){ cnt++; timp[cnt].first = ++stamp; comp[node] = cnt; if(comp[p] != 0){ bl[comp[node]][0] = comp[p]; } }else{ comp[node] = comp[p]; ///nu cnttt ca se modifica } for(auto x : v[node]){ if(!comp[x]){ assignComp(x, node); } } timp[comp[node]].second = stamp; } pii special[NMAX]; pii edges[NMAX]; void calc(int node, int p){ viz[node] = 1; for(auto x : v[node]){ if(!viz[x]){ calc(x, node); if(comp[node] != comp[x]){ surse[comp[node]] += surse[comp[x]]; deste[comp[node]] += deste[comp[x]]; } } } } int lca(int a, int b){ int r = a; int pas = nr_of_bits; while(pas >= 0){ int nxt = bl[r][pas]; if(nxt != 0 && !par(nxt, b)) r = nxt; pas--; } if(!par(r, b)) r = bl[r][0]; return r; } int main() { int i; /// Poate sunt mai multe componente cin >> n >> m; for(i = 1; i <= m; i++){ int x, y; cin >> x >> y; v[x].push_back(y); v[y].push_back(x); edges[i] = {x, y}; } for(i = 1; i <= n; i++) if(!lvl[i]) DFS(i, 0); for(i = 1; i <= n; i++) if(!comp[i]) assignComp(i, 0); for(int j = 1; j <= nr_of_bits; j++){ for(int i = 1; i <= n; i++){ bl[i][j] = bl[bl[i][j - 1]][j - 1]; } } int q; cin >> q; for(i = 1; i <= q; i++){ int x, y; cin >> x >> y; special[i] = {x, y}; if(comp[x] == comp[y]) continue; if(par(comp[x], comp[y])){ deste[comp[y]]++; ///se termina de adunat la deste[comp[x]]--; continue; } if(par(comp[y], comp[x])){ surse[comp[x]]++; ///se termina de adunat la surse[comp[y]]--; continue; } surse[comp[x]]++; deste[comp[y]]++; deste[lca(comp[x], comp[y])]--; surse[lca(comp[x], comp[y])]--; } for(i = 1; i <= n; i++){ if(!viz[i]) calc(i, 0); } for(i = 1; i <= m; i++){ int x = edges[i].first; int y = edges[i].second; if(lvl[x] > lvl[y]){ swap(x, y); } if(parent[y] != x){ cout << "B"; continue; } if(dp[y] != 0){ cout << "B"; continue; } if(!deste[comp[y]] && !surse[comp[y]]){ cout << "B"; continue; } if(surse[comp[y]] > 0){ if(y == edges[i].first){ cout << "R"; }else{ cout << "L"; } continue; } if(y == edges[i].first){ cout << "L"; }else{ cout << "R"; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...