Submission #1005155

#TimeUsernameProblemLanguageResultExecution timeMemory
1005155RifalOne-Way Streets (CEOI17_oneway)C++14
0 / 100
1 ms7512 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; int n, m; vector<int> v[Max]; set<int> st[Max]; map<pair<int,int>,int> mp, cnt; vector<int> now; bool vis[Max]; int nod; void dfs(int s) { vis[s] = 1; // cout << s << endl; if(st[nod].find(s) != st[nod].end()) { for(int i = now.size()-1; i >= 1; i--) { // cout << now[i-1] << ' ' << now[i] << 'r' << endl; if(mp[{now[i],now[i-1]}] == 0) { mp[{now[i],now[i-1]}] = 3; } if(mp[{now[i-1],now[i]}] == 0) { mp[{now[i-1],now[i]}] = 2; } } } for(auto i : v[s]) { if(vis[i] == 0) { cnt[{s,i}]--; cnt[{i,s}]--; now.push_back(i); dfs(i); now.pop_back(); } else if(cnt[{s,i}] > 0) { cnt[{s,i}]--; cnt[{i,s}]--; int last = i; for(int j = now.size()-1; j >= 0; j--) { mp[{now[j],last}] = 1; mp[{last,now[j]}] = 1; last = now[j]; if(now[j] == i) { break; } } } } } int main() { ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0); 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; vector<int> vv; while(p--) { int a, b; cin >> a >> b; st[a].insert(b); vv.push_back(a); } for(int i = 0; i < vv.size(); i++) { for(int j = 1; j <= n; j++) { vis[j] = 0;} for(int j = 0; j < m; j++) { cnt[{edge[j].fi,edge[j].se}]++; cnt[{edge[j].se,edge[j].fi}]++; } nod = vv[i]; now.push_back(nod); dfs(vv[i]); now.pop_back(); } for(int i = 0; i < m; i++) { int ans = mp[{edge[i].fi,edge[i].se}]; // cout << ans << endl; // cout << edge[i].fi << ' ' << edge[i].se << 'l' << endl; if(ans <= 1) { cout << 'B'; } else if(ans == 2) { cout << 'R'; } else { cout << 'L'; } } cout << endl; return 0; }

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:83:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int i = 0; i < vv.size(); i++) {
      |                    ~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...