Submission #1012558

#TimeUsernameProblemLanguageResultExecution timeMemory
1012558MODDIOne-Way Streets (CEOI17_oneway)C++14
100 / 100
137 ms30868 KiB
#include <bits/stdc++.h> #include <fstream> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #define endl '\n' #define mod 1000000007 #define INF 1000000000 #define INF2 2000000000 #define fi first #define se second using namespace std; double const EPS = 1e-14; const int P = 1007; typedef long long ll; using namespace __gnu_pbds; typedef long long ll; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // find_by_order, order_of_key const int Max = 1e5 + 5; vector<int> v[Max]; int sta[Max], low[Max], par[Max]; int tim = 0, cntx = 0, cnty = 0; map<pair<int,int>,int> mp, check; bool vis[Max], ok = false; int okx[Max], oky[Max]; void dfs(int s, int p) { tim++; vis[s] = 1; sta[s] = tim; low[s] = tim; for(auto i : v[s]) { if(vis[i] == 0) { dfs(i,s); low[s] = min(low[s],low[i]); okx[s]+=okx[i]; //you need to keep track of the count of left ends in the given subtree oky[s]+=oky[i]; //you need to keep track of the count of right ends in the given subtree if(low[i] > sta[s]) { if(okx[i] > oky[i]) { //if there are more left than right ends in the subtree of i, this means that one path leaves its subtree across the bridge and the edge needs to be directed from i to s mp[{i,s}] = 2; mp[{s,i}] = 3; } else if(okx[i] < oky[i]) { //if there are more right than left ends in the subtree of i, this means that one path enters its subtree across the bridge and the edge needs to be directed from s to i mp[{s,i}] = 2; mp[{i,s}] = 3; } } } else if(i != p || par[s] > 0){ low[s] = min(sta[i],low[s]); } else if(i == p) { par[s]++; } } cntx += okx[s]; cnty += oky[s]; } int main() { ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0); int n, m; cin >> n >> m; pair<int,int> edge[m]; for(int i = 0; i < m; i++) { int a, b; cin >> a >> b; edge[i].fi = a, edge[i].se = b; v[a].push_back(b); v[b].push_back(a); } int p; cin >> p; while(p--) { int a, b; cin >> a >> b; okx[a]++; oky[b]++; } for(int i = 1; i <= n; i++) { if(vis[i] == 0) { cntx = 0; cnty = 0; dfs(i,0); } } for(int i = 0; i < m; i++) { if(mp[{edge[i].fi,edge[i].se}] == 0) cout << 'B'; else if(mp[{edge[i].fi,edge[i].se}] == 3) cout << 'L'; else cout << 'R'; } cout << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...