oj.uz

Submission #521409

# Submission time Handle Problem Language Result Execution time Memory
521409 2022-02-02T05:22:25 Z Wayne_Yan One-Way Streets (CEOI17_oneway) C++17
60 / 100
 3000 ms 26152 KB 
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

typedef int64_t ll;
typedef long double ld;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb emplace_back
#define mp make_pair
#define mt make_tuple
#define pii pair<int,int>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define RF(n) RFi(i,n)
#define RFi(i,n) RFl(i,0,n)
#define RFl(i,l,n) for(int i=n-1;i>=l;i--)
#define all(v) begin(v),end(v)
#define siz(v) (ll(v.size()))
#define get_pos(v,x) (lower_bound(all(v),x)-begin(v))
#define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v))
#define mem(v,x) memset(v,x,sizeof v)
#define ff first
#define ss second
#define mid ((l+r)>>1)
#define RAN(a,b) uniform_int_distribution<int> (a, b)(rng)
#define debug(x) (cerr << (#x) << " = " << x << "\n")
#define cmax(a,b) (a = max(a,b))
#define cmin(a,b) (a = min(a,b))

template <typename T> using max_heap = __gnu_pbds::priority_queue<T,less<T> >;
template <typename T> using min_heap = __gnu_pbds::priority_queue<T,greater<T> >;
template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

const int maxN = 1e5+10;
vector<int> edge[maxN];
int depth[maxN];
int low[maxN];
bool visited[maxN];
stack<int> st;
int bcc[maxN];

vector<int> t_edge[maxN];

void tarjan(int c, int p){
  depth[c] = (p ? depth[p] + 1 : 0);
  low[c] = depth[c];
  visited[c] = true;
  st.push(c);
  
  int cnt_fa = 0;
  for(int i : edge[c]){
    if(i == p && !cnt_fa){
      cnt_fa = 1;
      continue;
    }
    if(visited[i]){
      cmin(low[c], depth[i]);
    }else{
      tarjan(i, c);
      cmin(low[c], low[i]);
    }
  }
  
  if(low[c] == depth[c]){
    int tmp = st.top();
    do{
      tmp = st.top();
      bcc[tmp] = c;
      st.pop();
    }while(tmp != c);
  }
}

int ST[18][maxN];
int fa[maxN];

pii tab[maxN];
char ans[maxN];

int dsu[2][maxN]; // 0 down, 1 up.

int query(int i, int a){
  return dsu[i][a] == a ? a : dsu[i][a] = query(i, dsu[i][a]);
}

void merge(int i, int a, int b){
  if(query(i, a) != query(i, b)) dsu[i][query(i, a)] = query(i, b);
}

int t_depth[maxN];
bool t_visited[maxN];

void dfs(int c, int p){
  t_visited[c] = true;
  t_depth[c] = ( p ? t_depth[p] + 1 : 0);
  for(int i : t_edge[c]){
    if(i == p) continue;
    dfs(i, c);
  }
}


int LCA(int x, int y){
  if(t_depth[x] < t_depth[y]) swap(x,y);
  int c = t_depth[x] - t_depth[y];
  F(18) if( (c >> i) & 1) x = ST[i][x];
  assert(t_depth[x] == t_depth[y]);
  
  if( x == y) return x;

  RF(18){
    if( ST[i][x] && ST[i][y] && ST[i][x] != ST[i][y]){
      x = ST[i][x];
      y = ST[i][y];
    }
  }
  x = ST[0][x];
  y = ST[0][y];
  assert( x == y );
  return x;
}

void process(int x, int y){
  int c = LCA(x,y);
  while( t_depth[x] > t_depth[c] ){
    if(dsu[1][x] != x){
      dsu[1][x] = x;
    }else{
      merge(1, x, ST[0][x]);
      x = ST[0][x];
    }
  }
  while( t_depth[y] > t_depth[c] ){
    if(dsu[0][y] != y){
      dsu[0][y] = y;
    }else{
      merge(0, y, ST[0][y]);
      y = ST[0][y];
    }
  }
}


signed main(){
  
  iota(dsu[0], dsu[0] + maxN, 0);
  iota(dsu[1], dsu[1] + maxN, 0);

  int n, m;
  cin >> n >> m;
  F(m){
    int x,y;
    cin >> x >> y;
    edge[x].pb(y);
    edge[y].pb(x);
    tab[i] = mp(x,y);
  }

  F(n) if(!visited[i+1]) tarjan(i+1, 0);
  
  Fi(x, m){
    auto [i,j] = tab[x];
    if(bcc[i] != bcc[j]){
      t_edge[bcc[i]].pb(bcc[j]);
      t_edge[bcc[j]].pb(bcc[i]);
      if(depth[bcc[i]] > depth[bcc[j]]){
        ST[0][bcc[i]] = fa[bcc[i]] = bcc[j];
      }else{
        ST[0][bcc[j]] = fa[bcc[j]] = bcc[i];
      }
      //printf("(%d, %d)\n", bcc[i], bcc[j]);
    }
  }
  
  Fl(i, 1, n+1){
    if(!t_visited[bcc[i]]) dfs( bcc[i], 0);
  }

  Fl(i, 1, 18){
    Fi(j, maxN){
      ST[i][j] = ST[i-1][ST[i-1][j]];
    }
  }

  int p;
  cin >> p;
  
  F(p){
    int x,y;
    cin >> x >> y;
    x = bcc[x], y = bcc[y];
    process(x,y);
  }
  
  Fi(x, m){
    auto [i,j] = tab[x];
    i = bcc[i], j = bcc[j];
    if(i != j){
      if(query(0, i) == query(0, j)){
        if(t_depth[i] < t_depth[j]){
          ans[x] = 'R';
        }else{
          ans[x] = 'L';
        }
      }else if(query(1,i) == query(1, j)){
        if(t_depth[i] < t_depth[j]){
          ans[x] = 'L';
        }else{
          ans[x] = 'R';
        }
      }else{
        ans[x] = 'B';
      }

      assert(!((query(0, i) == query(0, j)) && (query(1, i) == query(1, j))));
    }else{
      ans[x] = 'B';
    }
  }
  
  F(m) printf("%c", ans[i]);
  //F(m) assert(ans[i]);
   
  return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12364 KB Output is correct
2 Correct 7 ms 12492 KB Output is correct
3 Correct 8 ms 12456 KB Output is correct
4 Correct 8 ms 12464 KB Output is correct
5 Correct 9 ms 12532 KB Output is correct
6 Correct 9 ms 12592 KB Output is correct
7 Correct 8 ms 12592 KB Output is correct
8 Correct 8 ms 12592 KB Output is correct
9 Correct 8 ms 12468 KB Output is correct
10 Correct 8 ms 12492 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12364 KB Output is correct
2 Correct 7 ms 12492 KB Output is correct
3 Correct 8 ms 12456 KB Output is correct
4 Correct 8 ms 12464 KB Output is correct
5 Correct 9 ms 12532 KB Output is correct
6 Correct 9 ms 12592 KB Output is correct
7 Correct 8 ms 12592 KB Output is correct
8 Correct 8 ms 12592 KB Output is correct
9 Correct 8 ms 12468 KB Output is correct
10 Correct 8 ms 12492 KB Output is correct
11 Correct 72 ms 17484 KB Output is correct
12 Correct 74 ms 18976 KB Output is correct
13 Correct 81 ms 20468 KB Output is correct
14 Correct 89 ms 22124 KB Output is correct
15 Correct 93 ms 22720 KB Output is correct
16 Correct 108 ms 23484 KB Output is correct
17 Correct 152 ms 24992 KB Output is correct
18 Correct 110 ms 23576 KB Output is correct
19 Correct 142 ms 26152 KB Output is correct
20 Correct 75 ms 18608 KB Output is correct
21 Correct 74 ms 18808 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12364 KB Output is correct
2 Correct 7 ms 12492 KB Output is correct
3 Correct 8 ms 12456 KB Output is correct
4 Correct 8 ms 12464 KB Output is correct
5 Correct 9 ms 12532 KB Output is correct
6 Correct 9 ms 12592 KB Output is correct
7 Correct 8 ms 12592 KB Output is correct
8 Correct 8 ms 12592 KB Output is correct
9 Correct 8 ms 12468 KB Output is correct
10 Correct 8 ms 12492 KB Output is correct
11 Correct 72 ms 17484 KB Output is correct
12 Correct 74 ms 18976 KB Output is correct
13 Correct 81 ms 20468 KB Output is correct
14 Correct 89 ms 22124 KB Output is correct
15 Correct 93 ms 22720 KB Output is correct
16 Correct 108 ms 23484 KB Output is correct
17 Correct 152 ms 24992 KB Output is correct
18 Correct 110 ms 23576 KB Output is correct
19 Correct 142 ms 26152 KB Output is correct
20 Correct 75 ms 18608 KB Output is correct
21 Correct 74 ms 18808 KB Output is correct
22 Execution timed out 3027 ms 25072 KB Time limit exceeded
23 Halted 0 ms 0 KB -