Submission #878689

#TimeUsernameProblemLanguageResultExecution timeMemory
878689Ghulam_JunaidOne-Way Streets (CEOI17_oneway)C++17
0 / 100
3 ms12124 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int n, m, p, deg[N]; vector<int> g[N]; set<int> waiting_in[N], waiting_out[N]; map<pair<int, int>, int> edge; vector<pair<int, int>> edges; int main(){ cin >> n >> m; string s; for (int i=0; i<m; i++){ int u, v; cin >> u >> v; if (u != v){ g[u].push_back(v); g[v].push_back(u); deg[u]++; deg[v]++; } edge[{u, v}] = edge[{v, u}] = i; edges.push_back({u, v}); s += 'B'; } cin >> p; for (int i=0; i<p; i++){ int u, v; cin >> u >> v; waiting_in[v].insert(u); waiting_out[u].insert(v); } queue<int> q; for (int i=1; i<=n; i++) if (deg[i] == 1) q.push(i); while (!q.empty()){ int v = q.front(); int u = g[v][0]; q.pop(); if (deg[v] != 1) continue; deg[v]--; deg[u]--; int id = edge[{v, u}]; // cout << v << " prev char = " << s[id] << " new char = "; // cout << "id = " << id << endl; if (waiting_in[v].size()){ // cout << "here 1" << endl; if (edges[id].first == u) s[id] = 'R'; else s[id] = 'L'; for (int x : waiting_in[v]){ // v is waiting in for x waiting_out[x].erase(v); if (x == u) continue; waiting_in[u].insert(x); waiting_out[x].insert(u); } waiting_in[v].clear(); } if (waiting_out[v].size()){ // cout << "here 2" << endl; if (edges[id].first == v) s[id] = 'R'; else s[id] = 'L'; for (int x : waiting_out[v]){ waiting_in[x].erase(v); if (u == x) continue; waiting_out[u].insert(x); waiting_in[x].insert(u); } waiting_out[v].clear(); } if (deg[u] == 1) q.push(u); // cout << s[id] << endl; } cout << s << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...