oj.uz

Submission #237818

# Submission time Handle Problem Language Result Execution time Memory
237818 2020-06-08T23:15:45 Z Nucleist One-Way Streets (CEOI17_oneway) C++14
100 / 100
 814 ms 83940 KB 
#include <bits/stdc++.h> 
using namespace std; 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll long long
#define INF 1000000000
#define MOD 1000000007
#define pb push_back
#define ve vector<ll>
#define dos pair<ll,ll>
#define vedos vector<dos>
#define rand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define EPS 0.000001
struct greateri
{
    template<class T>
    bool operator()(T const &a, T const &b) const { return a > b; }
};
void setIO(string s) {
  ios_base::sync_with_stdio(0); cin.tie(0); 
  freopen((s+".in").c_str(),"r",stdin);
  freopen((s+".out").c_str(),"w",stdout);
}
ll tin[200001],tlow[200001],vis[200001],vis1[200001],dep[200001],pa[200001][30];
ve gr[200001],gr1[200001],tr[200001];
set<dos>brid;
ll n,m,p;
char ans[200001];
map<dos,ve>g;
ll timer,l;
ll col[200001];
void dfs(ll node,ll p){
  vis[node]=1;
  tin[node]=timer++;
  tlow[node]=tin[node];
  for(auto it:gr[node]){
    if(it==p || it==node)continue;
    if(vis[it]){
      tlow[node]=min(tin[it],tlow[node]);
    }
    else{
      dfs(it,node);
      tlow[node]=min(tlow[node],tlow[it]);
      if(tlow[it]>tin[node]){
        brid.insert({min(node,it),max(node,it)});
      }
    }
  }
}
void dfs1(ll node,ll co){
  col[node]=co;
  vis1[node]=1;
  for(auto it:gr1[node]){
    if(!vis1[it]){
      dfs1(it,co);
    }
  }
}
void dfk(ll node,ll p,ll ka){
  vis1[node]=1;
  tin[node]=timer++;
  dep[node]=ka;
  pa[node][0]=p;
  for (ll i = 1; i <= l; ++i)
  {
    pa[node][i]=pa[pa[node][i-1]][i-1];
  }
  for(auto it:tr[node]){
    if(it!=p){
      dfk(it,node,ka+1);
    }
  }
  tlow[node]=timer++;
}
bool is_anc(ll u,ll v){
  if(tin[u]<=tin[v] && tlow[u]>=tlow[v])return 1;
  return 0;
}
ll lca(ll u,ll v){
  if(is_anc(u,v))return u;
  if(is_anc(v,u))return v;
  for (ll i = l; i >= 0; --i)
  {
    if(!is_anc(pa[u][i],v)){
      u=pa[u][i];
    }
  }
  return pa[u][0];
}
ll parent[200000], depth[200000], heavy[200000], head[200000], pos[200000];
ll cur_pos;
ll lom(ll v) {
    vis1[v]=1;
    ll size = 1;
    ll max_c_size = 0;
    for (ll c : tr[v]) {
        if (c != parent[v]) {
            parent[c] = v, depth[c] = depth[v] + 1;
            ll c_size = lom(c);
            size += c_size;
            if (c_size > max_c_size)
                max_c_size = c_size, heavy[v] = c;
        }
    }
    return size;
}

ll decompose(ll v, ll h) {
    head[v] = h, pos[v] = cur_pos++;
    if (heavy[v] != -1)
      decompose(heavy[v], h);
    for (ll c : tr[v]) {
        if (c != parent[v] && c != heavy[v])
          decompose(c, c);
    }
}
ll bit[200001];
void add(ll idx, ll val) {
    for (idx; idx <= n; idx += idx & -idx)
        bit[idx] += val;
}

void range_add(ll l, ll r, ll val) {
    add(l, val);
    add(r + 1, -val);
}

ll point_query(ll idx) {
    ll ret = 0;
    for (idx; idx > 0; idx -= idx & -idx)
        ret += bit[idx];
    return ret;
}
void query(ll a, ll b,ll val) {
    ll res = 0;
    for (; head[a] != head[b]; b = parent[head[b]]) {
        if (depth[head[a]] > depth[head[b]])
            swap(a, b);
        //debugs(pos[head[b]],pos[b])
        //debug(val)
        range_add(pos[head[b]]+1, pos[b]+1,val);
        //debug(point_query(pos[head[b]]+1))
        //res = max(res, cur_heavy_path_max);
    }
    if (depth[a] > depth[b])
      swap(a, b);
    //debugs(a,b)
    //debug(val)
    range_add(pos[a]+1, pos[b]+1,val);
    return;
}
int main()
{
  //flash;
  cin>>n>>m;
  l=log2(n);
  vedos ed;
  for (ll i = 0; i < m; ++i)
  {
    ll u,v;
    cin>>u>>v;
    u--,v--;
    if(u==v){
      ans[i]='B';
    }
    else{
      ed.pb({u,v});
      gr[u].pb(v),gr[v].pb(u);
      if(u>v)swap(u,v);
      g[{u,v}].pb(i);
    }   
  }
  for(auto it:g){
    if(it.second.size()>1){
      for(auto it1:it.second){
        ans[it1]='B';
      }
    }
  }
  for (int i = 0; i < n; ++i)
  {
    if(!vis[i])dfs(i,-1);
  }
  set<dos>rem;
  for(auto it:brid){
    if(g[{it.first,it.second}].size()>1)rem.insert(it);
  }
  for(auto it:rem)brid.erase(it);
  for(auto it:ed){
    auto u=it.first,v=it.second;
    if(u>v)swap(u,v);
    if(brid.find({u,v})==brid.end()){
      gr1[u].pb(v),gr1[v].pb(u);
    }
  }
  ll ci=1;
  for (ll i = 0; i < n; ++i)
  {
    if(!vis1[i]){
      dfs1(i,ci);
      ci++;
    }
  }
  timer=0;
  for(auto it:brid){
    tr[col[it.first]].pb(col[it.second]);
    tr[col[it.second]].pb(col[it.first]);
  }
  memset(vis1,0,sizeof vis1);
  for (int i = 1; i < ci; ++i)
  {
    if(!vis1[i]){timer=0,dfk(i,i,0);}
  }
  ll q;
  cin>>q;
  memset(heavy,-1,sizeof heavy);   
  memset(vis1,0,sizeof vis1);  
  for (int i = 1; i < ci; ++i)
  {
    if(!vis1[i]){lom(i),decompose(i,i);}
  }
  while(q--){
    ll u,v;
    cin>>u>>v;
    u--,v--;
    if(col[u]==col[v])continue;
    ll dol=lca(col[u],col[v]);
    query(col[u],dol,1);
    query(col[v],dol,-1);
  }
  for (ll i = 0; i < ed.size(); ++i)
  {
    auto u=ed[i].first,v=ed[i].second;
    if(u>v)swap(u,v);
    if(ans[i]!='B' && brid.find({u,v})!=brid.end() && col[u]!=col[v]){
      if(dep[col[u]]<=dep[col[v]])swap(u,v);
      ll cur=point_query(pos[col[u]]+1);
      if(cur>0){
        if(ed[i].first==u)ans[i]='R';
        else ans[i]='L';
      } 
      else if(cur<0){
        if(ed[i].first==u)ans[i]='L';
        else ans[i]='R';
      }
      else ans[i]='B';
    }
    else ans[i]='B';
  }
  for (ll i = 0; i < m; ++i)
  {
    cout<<ans[i];
  }
  return 0;
}
//code the AC sol !
// BS/queue/map

Compilation message

oneway.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
oneway.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
oneway.cpp: In function 'long long int decompose(long long int, long long int)':
oneway.cpp:122:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
oneway.cpp: In function 'void add(long long int, long long int)':
oneway.cpp:125:13: warning: statement has no effect [-Wunused-value]
     for (idx; idx <= n; idx += idx & -idx)
             ^
oneway.cpp: In function 'long long int point_query(long long int)':
oneway.cpp:136:13: warning: statement has no effect [-Wunused-value]
     for (idx; idx > 0; idx -= idx & -idx)
             ^
oneway.cpp: In function 'void query(long long int, long long int, long long int)':
oneway.cpp:141:8: warning: unused variable 'res' [-Wunused-variable]
     ll res = 0;
        ^~~
oneway.cpp: In function 'int main()':
oneway.cpp:237:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (ll i = 0; i < ed.size(); ++i)
                  ~~^~~~~~~~~~~
oneway.cpp: In function 'void setIO(std::__cxx11::string)':
oneway.cpp:27:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen((s+".in").c_str(),"r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:28:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen((s+".out").c_str(),"w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 17664 KB Output is correct
2 Correct 15 ms 17664 KB Output is correct
3 Correct 16 ms 17920 KB Output is correct
4 Correct 17 ms 18176 KB Output is correct
5 Correct 17 ms 18304 KB Output is correct
6 Correct 17 ms 17792 KB Output is correct
7 Correct 17 ms 18304 KB Output is correct
8 Correct 17 ms 18224 KB Output is correct
9 Correct 19 ms 17792 KB Output is correct
10 Correct 16 ms 17792 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 17664 KB Output is correct
2 Correct 15 ms 17664 KB Output is correct
3 Correct 16 ms 17920 KB Output is correct
4 Correct 17 ms 18176 KB Output is correct
5 Correct 17 ms 18304 KB Output is correct
6 Correct 17 ms 17792 KB Output is correct
7 Correct 17 ms 18304 KB Output is correct
8 Correct 17 ms 18224 KB Output is correct
9 Correct 19 ms 17792 KB Output is correct
10 Correct 16 ms 17792 KB Output is correct
11 Correct 251 ms 38884 KB Output is correct
12 Correct 277 ms 40548 KB Output is correct
13 Correct 310 ms 43748 KB Output is correct
14 Correct 442 ms 52716 KB Output is correct
15 Correct 441 ms 56804 KB Output is correct
16 Correct 510 ms 75880 KB Output is correct
17 Correct 473 ms 78436 KB Output is correct
18 Correct 646 ms 76496 KB Output is correct
19 Correct 533 ms 80100 KB Output is correct
20 Correct 248 ms 40420 KB Output is correct
21 Correct 250 ms 39780 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 17664 KB Output is correct
2 Correct 15 ms 17664 KB Output is correct
3 Correct 16 ms 17920 KB Output is correct
4 Correct 17 ms 18176 KB Output is correct
5 Correct 17 ms 18304 KB Output is correct
6 Correct 17 ms 17792 KB Output is correct
7 Correct 17 ms 18304 KB Output is correct
8 Correct 17 ms 18224 KB Output is correct
9 Correct 19 ms 17792 KB Output is correct
10 Correct 16 ms 17792 KB Output is correct
11 Correct 251 ms 38884 KB Output is correct
12 Correct 277 ms 40548 KB Output is correct
13 Correct 310 ms 43748 KB Output is correct
14 Correct 442 ms 52716 KB Output is correct
15 Correct 441 ms 56804 KB Output is correct
16 Correct 510 ms 75880 KB Output is correct
17 Correct 473 ms 78436 KB Output is correct
18 Correct 646 ms 76496 KB Output is correct
19 Correct 533 ms 80100 KB Output is correct
20 Correct 248 ms 40420 KB Output is correct
21 Correct 250 ms 39780 KB Output is correct
22 Correct 681 ms 79716 KB Output is correct
23 Correct 703 ms 77732 KB Output is correct
24 Correct 709 ms 77668 KB Output is correct
25 Correct 814 ms 83940 KB Output is correct
26 Correct 670 ms 79204 KB Output is correct
27 Correct 677 ms 77692 KB Output is correct
28 Correct 156 ms 26188 KB Output is correct
29 Correct 333 ms 40932 KB Output is correct
30 Correct 351 ms 41060 KB Output is correct
31 Correct 411 ms 41572 KB Output is correct
32 Correct 407 ms 53220 KB Output is correct