Submission #574057

#	Time	Username	Problem	Language	Result	Execution time	Memory
574057		MohammadAghil	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	211 ms	26912 KiB

oneway

      #include <bits/stdc++.h>
//   #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
    using namespace std;
  typedef long long ll;
   typedef pair<int, int> pp;
    #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
      #define per(i,r,l) for(int i = (r); i >= (l); i--)
        #define rep(i,l,r) for(int i = (l); i < (r); i++)
           #define all(x) x.begin(), x.end()
              #define sz(x) (int)(x).size()
                  #define pb push_back
                      #define ss second
                           #define ff first
                                   void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 1e5 + 5, lg = 21, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}
 
vector<int> adj[maxn];
int par[maxn], cnt[maxn];
vector<pp> his;
 
int get(int x){ return par[x] == -1? x: get(par[x]); }
bool unite(int u, int v){
     u = get(u), v = get(v);
     if(u == v) return his.pb({-1, -1}), false;
     if(cnt[u] < cnt[v]) swap(u, v);
     par[v] = u, cnt[u] += cnt[v];
     return his.pb({v, u}), true;
}
void undo(){
     auto[v, u] = his.back(); his.pop_back();
     if(u + 1) par[v] = -1, cnt[u] -= cnt[v];
}
 
pp edge[maxn];
bool cut_edge[maxn], vis[maxn];
 
void slv(int l, int r){
     if(l + 1 == r) {
          cut_edge[l] = get(edge[l].ff) != get(edge[l].ss);
          return;
     }
     int mid = (l + r)>>1;
     rep(i,mid,r) unite(edge[i].ff, edge[i].ss);
     slv(l, mid);
     rep(i,mid,r) undo();
     rep(i,l,mid) unite(edge[i].ff, edge[i].ss);
     slv(mid, r);
     rep(i,l,mid) undo();
}
 
vector<int> adj2[maxn];
int st[maxn];
map<pp, bool> is;
 
void add_query(int u, int v){
     st[u]++, st[v]--;
}
 
void dfs(int r, int p){
     vis[r] = true;
     for(int c: adj2[r]) if(c - p){
          dfs(c, r);
          st[r] += st[c];
     }
     if(st[r]){
          if(st[r] > 0) is[{r, p}] = true;
          else is[{p, r}] = true;
     }
}
 
int main(){
     cin.tie(0) -> sync_with_stdio(0);
     int n, m; cin >> n >> m;
     fill(par, par + n, -1);
     fill(cnt, cnt + n, 1);
     rep(i,0,m){
          cin >> edge[i].ff >> edge[i].ss; edge[i].ff--, edge[i].ss--;
     }
     slv(0, m);
     rep(i,0,m) if(!cut_edge[i]) unite(edge[i].ff, edge[i].ss);
     vector<int> grp(n, -1); int id = 0;
     rep(i,0,n){
          if(grp[get(i)] == -1) grp[get(i)] = id++;
          grp[i] = grp[get(i)];
     }
     rep(i,0,m) if(cut_edge[i]) {
          adj2[grp[edge[i].ff]].pb(grp[edge[i].ss]);
          adj2[grp[edge[i].ss]].pb(grp[edge[i].ff]);
     }
     int q; cin >> q;
     while(q--){
          int u, v; cin >> u >> v; u = grp[--u], v = grp[--v];
          add_query(u, v);
     }
     rep(i,0,n) if(!vis[i]) dfs(i, i);
     vector<int> ans(m);
     rep(i,0,m){
          if(cut_edge[i]){
               if(is.count({grp[edge[i].ff], grp[edge[i].ss]})) ans[i] = 1;
               else if(is.count({grp[edge[i].ss], grp[edge[i].ff]})) ans[i] = 2;
          }
     }
     for(int c: ans) cout << (c?(c&1?'R':'L'):'B');
     return 0; 
}

Compilation message (stderr)

oneway.cpp: In function 'void undo()':
oneway.cpp:33:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |      auto[v, u] = his.back(); his.pop_back();
      |          ^
oneway.cpp: In function 'int main()':
oneway.cpp:95:38: warning: operation on 'u' may be undefined [-Wsequence-point]
   95 |           int u, v; cin >> u >> v; u = grp[--u], v = grp[--v];
oneway.cpp:95:52: warning: operation on 'v' may be undefined [-Wsequence-point]
   95 |           int u, v; cin >> u >> v; u = grp[--u], v = grp[--v];

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40