oj.uz

Submission #597681

# Submission time Handle Problem Language Result Execution time Memory
597681 2022-07-16T14:35:32 Z codebuster_10 One-Way Streets (CEOI17_oneway) C++17
100 / 100
 385 ms 43756 KB 
#include <bits/stdc++.h>
#define int int64_t //be careful about this 

using namespace std;

#define vt vector 
#define ar array 
#define pr pair 

#define f first 
#define s second

#define pb push_back
#define eb emplace_back

#define fr(i,a,b) for(int i = (a); i < (b); ++i)
#define rf(i,a,b) for(int i = (b)-1; i >= (a); --i)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))

namespace IN{
  template<class T> void re(vector<T> &A);
  template<class S,class T> void re(pair<S,T> &A);
  template<class T,size_t N> void re(array<T,N> &A);

  template<class T> void re(T& x){ 
    cin >> x;}
  template<class H, class... T> void re(H& h, T&... t){ 
    re(h); re(t...);}

  template<class T> void re(vector<T> &A){ 
    for(auto& x : A) re(x);}
  template<class S,class T> void re(pair<S,T> &A){ 
      re(A.first); re(A.second);}
  template<class T,size_t N> void re(array<T,N> &A){
    for(int i = 0; i < N; ++i)  re(A[i]);}
}

namespace OUT{
  template<class T>
  void __p(const T& a){ cout<<a; }
  template<class T, class F>
  void __p(const pair<T, F>& a){ cout<<"{"; __p(a.first); cout<<","; __p(a.second); cout<<"}\n"; }
  template<class T, size_t N>
  void __p(const array<T,N>& a){ cout<<"{"; for(int i=0;i<N;++i)__p(a[i]),cout<<",}\n"[i+1==N]; }
  template<class T>
  void __p(const vector<T>& a){
    cout<<"{";for(auto it=a.begin();it<a.end();it++)__p(*it),cout<<",}\n"[it+1==a.end()]; }
  template<class T, class ...Arg>
  void __p(T a1, Arg ...a){__p(a1); __p(a...); }
  template<class Arg1>
  void __f(const char *s, Arg1 &&arg1){ cout<<s<<" : "; __p(arg1); cout<<endl; }
  template<class Arg1, class ... Args>
  void __f(const char *ss, Arg1 &&arg1, Args &&... args){
    int b=0,i=0; do{ if(ss[i]=='(') b++; if(ss[i]==')') b--; i++;}while(!(ss[i]==','&&b==0));
    const char *comma=ss+i; cout.write(ss,comma-ss)<<" : ";__p(arg1);cout<<" | ";__f(comma+1,args...);}
  #define trace(...) cout<<"Line:"<<__LINE__<<"  ", __f(#__VA_ARGS__, __VA_ARGS__)
}


namespace FUNC{
  void IO(string s = ""){
    ios_base::sync_with_stdio(NULL); 
    cin.tie(nullptr); 
    cout.precision(20); 
    cout << fixed;
    if(!s.empty()){
      freopen((s+".in").c_str(),"r",stdin);
      freopen((s+".out").c_str(),"w",stdout);
    }
  }

  const auto start_time = chrono::high_resolution_clock::now();
  void output_run_time(){
    // will work for ac,cc&&cf.
#ifndef ONLINE_JUDGE
    auto end_time = chrono::high_resolution_clock::now();
    chrono::duration<double> diff = end_time-start_time;
      cout << "\n\n\nTime Taken : " << diff.count();
#endif
  }

  template<class T> bool ckmin(T& a, const T& b){ 
    return b < a ? a = b, true : false; }
    
  template<class T> bool ckmax(T& a, const T& b){ 
    return a < b ? a = b, true : false; }

  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  int my_rand(int L, int R){ 
    return uniform_int_distribution<int>(L,R)(rng); }
  
  template<class T> int sz(const T& x){ 
    return int(x.size()); }

  template<class T> int lb(const vector<T>& vec,const T& val){
    return int(lower_bound(vec.begin(), vec.end(),val) - vec.begin()); }

  template<class T> int ub(const vector<T>& vec,const T& val){
    return int(upper_bound(vec.begin(), vec.end(),val) - vec.begin()); }

  constexpr int  dx[4] = {1,0,-1,0};
  constexpr int  dy[4] = {0,1,0,-1};
  constexpr char dr[4] = {'D','R','U','L'};

  constexpr long long INFLL1 = 1e16, INFLL2 = 9e18;
  constexpr int INF = 2e9;

  template<class T>
  vector<T> V(int n,T val){
    return vector<T> (n,val);
  }

  template<class T>
  vector<vector<T>> V(int n,int m,T val){
    return vector<vector<T>> (n,vector<T> (m,val));
  }

  template<class T>
  vector<vector<vector<T>>> V(int n,int m,int k,T val){
    return vector<vector<vector<T>>> (n,vector<vector<T>> (m,vector<T> (k,val)));
  }
}


using namespace IN;
using namespace OUT;
using namespace FUNC;












struct DSU {
  int n, z;
  // root node: -1 * component size
  // otherwise: parent
  vector<int> parent_or_size;

  DSU(int n_ = -1){
    if(n_ >= 0)
      init(n_);
  }

  void init(int n_){
    z = n = n_;
    parent_or_size.assign(n_, -1);
  } 

  bool merge(int a, int b){
    int x = leader(a), y = leader(b);
    if(x == y) 
      return false;
    if(-parent_or_size[x] < -parent_or_size[y]) 
      swap(x, y);
    parent_or_size[x] += parent_or_size[y];
    parent_or_size[y] = x;
    z--;
    return true;
  }

  bool same(int a, int b){
    return leader(a) == leader(b);
  }

  int leader(int a){
    if(parent_or_size[a] < 0) 
      return a;
    return parent_or_size[a] = leader(parent_or_size[a]);
  }

  int size(int a){
    return -parent_or_size[leader(a)];
  }
  
  vector<vector<int>> groups(){
    vector<int> leader_buf(n), group_size(n);
    for(int i = 0; i < n; i++){
      leader_buf[i] = leader(i);
      group_size[leader_buf[i]]++;
    }
    vector<vector<int>> result(n);
    for(int i = 0; i < n; i++){
      result[i].reserve(group_size[i]);
    }
    for(int i = 0; i < n; i++){
      result[leader_buf[i]].push_back(i);
    }
    result.erase(remove_if(result.begin(), result.end(),[&](const auto& v){return v.empty(); }),result.end());
    return result;
  }

  int comp(){
    return z;
  }
};

vt<pr<int,int>> bridges;
DSU dsu;


vector<vector<int>> two_edge_cc(const vector<vector<int>>& g_){

  struct E{
    int to,id;
  };

  int n = g_.size();

  vector<vector<E>> g(n);

  for(int i = 0, f = 0; i < n; ++i)
    for(auto j : g_[i])
      if(j < i){
        g[j].push_back({i,f});
        g[i].push_back({j,f++});
      }
    

  vector<int> depth(n,-1), up(n);
  dsu.init(n);

  auto dfs = [&](auto self,int node,int parent_id) -> bool {
    up[node] = depth[node];
    for(auto [child,id] : g[node])
      if(id != parent_id)
        if(depth[child] < 0){
          depth[child] = depth[node] + 1;
          if(!self(self,child,id)){
            dsu.merge(node,child);
          }else{
            bridges.pb({node,child});
          }
          up[node] = min(up[node],up[child]);
        }else{
          up[node] = min(up[node],depth[child]);
        }
      
    return up[node] == depth[node];
  }; 

  for(int i = 0; i < n; ++i)
    if(depth[i] < 0){
      depth[i] = 0;
      dfs(dfs,i,-1);
    }

  return dsu.groups();
}







signed main(){
  IO();

  int n,m;
  re(n,m);

  vt<vt<int>> g(n);
  vt<pr<int,int>> edges;
  fr(e,0,m){
    int u,v; re(u,v); --u,--v;
    edges.push_back({u,v});
    g[u].pb(v);
    g[v].pb(u);
  }

  two_edge_cc(g);

  vt<vt<int>> tree(n);

  set<pr<int,int>> chk;

  for(auto [u,v] : bridges){
    u = dsu.leader(u);
    v = dsu.leader(v);
    tree[u].pb(v);
    tree[v].pb(u);
    chk.insert({u,v});
  }

  int k;
  re(k);

  vt<int> val(n,0);

  while(k--){
    int u,v; re(u,v); --u,--v;
    u = dsu.leader(u);
    v = dsu.leader(v);
    val[u]++;
    val[v]--;
  }

  set<pr<int,int>> dir;

  vt<bool> vis(n,false);

  auto dfs = [&](auto self,int i,int parent) -> void {
    vis[i] = true;
    for(auto j : tree[i])
      if(j != parent){
        self(self,j,i);
        val[i] += val[j];
        if(val[j] > 0){
          dir.insert({j,i});
        }else if(val[j] < 0){
          dir.insert({i,j});
        }
      }
  };

  fr(i,0,n) if(!vis[dsu.leader(i)]) dfs(dfs,dsu.leader(i),-1);

  for(auto [u,v] : edges){
    int pu = dsu.leader(u), pv = dsu.leader(v);
    if(pu == pv){
      cout << "B";
    }else{
      assert(chk.count({pu,pv}) || chk.count({pv,pu}));
      if(dir.count({pu,pv})){
        cout << "R";
      }else if(dir.count({pv,pu})){
        cout << "L";
      }else{
        cout << "B";
      }
    }
  }
  


  // output_run_time();
  return 0;
}

Compilation message

oneway.cpp: In lambda function:
oneway.cpp:233:9: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
  233 |       if(id != parent_id)
      |         ^
oneway.cpp: In function 'void FUNC::IO(std::string)':
oneway.cpp:68:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |       freopen((s+".in").c_str(),"r",stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:69:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |       freopen((s+".out").c_str(),"w",stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 55 ms 15668 KB Output is correct
12 Correct 69 ms 18820 KB Output is correct
13 Correct 83 ms 22680 KB Output is correct
14 Correct 110 ms 27584 KB Output is correct
15 Correct 129 ms 29084 KB Output is correct
16 Correct 254 ms 27580 KB Output is correct
17 Correct 320 ms 31748 KB Output is correct
18 Correct 255 ms 27492 KB Output is correct
19 Correct 273 ms 34624 KB Output is correct
20 Correct 67 ms 20764 KB Output is correct
21 Correct 66 ms 19436 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 55 ms 15668 KB Output is correct
12 Correct 69 ms 18820 KB Output is correct
13 Correct 83 ms 22680 KB Output is correct
14 Correct 110 ms 27584 KB Output is correct
15 Correct 129 ms 29084 KB Output is correct
16 Correct 254 ms 27580 KB Output is correct
17 Correct 320 ms 31748 KB Output is correct
18 Correct 255 ms 27492 KB Output is correct
19 Correct 273 ms 34624 KB Output is correct
20 Correct 67 ms 20764 KB Output is correct
21 Correct 66 ms 19436 KB Output is correct
22 Correct 345 ms 35868 KB Output is correct
23 Correct 366 ms 31760 KB Output is correct
24 Correct 385 ms 31652 KB Output is correct
25 Correct 367 ms 43756 KB Output is correct
26 Correct 357 ms 34772 KB Output is correct
27 Correct 382 ms 31740 KB Output is correct
28 Correct 35 ms 8508 KB Output is correct
29 Correct 98 ms 20164 KB Output is correct
30 Correct 88 ms 19672 KB Output is correct
31 Correct 95 ms 20936 KB Output is correct
32 Correct 160 ms 26984 KB Output is correct