Submission #1367411

#TimeUsernameProblemLanguageResultExecution timeMemory
1367411coderg300711One-Way Streets (CEOI17_oneway)C++20
0 / 100
0 ms344 KiB
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pii pair<int,int>
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define pb push_back
#define sz(x) (int)(x).size()
#define rsz resize
#define ass assign
#define F(i,l,r) for(int i=(l);i<(r);++i)
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
template<typename T> using pqg = priority_queue<T, vector<T>, greater<T>>;
#define each(a,x) for(auto a:x)
#define FOR(i,a) for(int i=0;i<(a);i++)
#define ROF(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define eb emplace_back
#define ft front()
#define V vector

struct TECC{
  int n,k;
  V<V<int>> adj,t;
  V<bool> used;
  V<int> comp,order,low;
  using edge=pii;
  V<edge> br;
  void dfs(int x,int prv,int &c){
    used[x]=1;
    order[x]=c++;
    low[x]=n;
    bool mul=0;
    each(y,adj[x]){
      if(used[y]){
        if(y!=prv || mul)low[x]=min(low[x],order[y]);
        else mul=1;
        continue;
      }
      dfs(y,x,c);
      low[x]=min(low[x],low[y]);
    }
  }
  void dfs2(int x,int num){
    comp[x]=num;
    each(y,adj[x]){
      if(!!~comp[y])continue;
      if(order[x]<low[y]){
        br.pb({x,y});
        k++;
        dfs2(y,k);
      }else dfs2(y,num);
    }
  }
  TECC(const V<V<int>> &adj):adj(adj),n(sz(adj)),used(n),comp(n,-1),order(n),low(n),k(0){
    int c=0;
    FOR(i,n){
      if(used[i])continue;
      dfs(i,-1,c);
      dfs2(i,k);
      k++;
    }
  }
  void build_tree(){
    t.rsz(k);
    each(e,br){
      int x=comp[e.fi],y=comp[e.se];
      t[x].pb(y);
      t[y].pb(x);
    }
  }
};

const int LOG=20;
V<V<pii>> tree;
V<V<int>> upp;
V<int> dep,diff_up,diff_down;
string res;
V<pii> edges;
V<int> comp;

void dfs_lca(int u,int p,int d){
dep[u]=d;
upp[0][u]=p;
each(e,tree[u]){
  if(e.fi!=p)dfs_lca(e.fi,u,d+1);
}
}

int get_lca(int u,int v,int k){
  if(dep[u]<dep[v])swap(u,v);
  ROF(i,0,LOG){
    if(!!~upp[i][0] && dep[upp[i][u]]>=dep[v])u=upp[i][u];
  }
  if(u==v)return u;
  ROF(i,0,LOG){
    if(upp[i][u]!=upp[i][v]){
      u=upp[i][u];
      v=upp[i][v];
    }
  }
  return upp[0][u];
}

void dfs_solve(int u,int p){
  each(e,tree[u]){
    int v=e.fi,id=e.se;
    if(v==p)continue;
    dfs_solve(v,u);
    if(diff_up[v]>0)res[id]=(comp[edges[id].fi]==v?'L':'R');
    else if(diff_down[v]>0)res[id]=(comp[edges[id].fi]==u?'L':'R');
    diff_up[u]+=diff_up[v];
    diff_down[u]+=diff_down[v];
  }
}

void solve(){
int n,m;
cin>>n>>m;
edges.rsz(m);
V<V<int>> adj(n);
FOR(i,m){
  cin>>edges[i].fi>>edges[i].se;
  --edges[i].fi;
  --edges[i].se;
  adj[edges[i].fi].pb(edges[i].se);
  adj[edges[i].se].pb(edges[i].fi);
}
TECC tecc(adj);
comp=tecc.comp;
tree.ass(tecc.k,V<pii>());
res.ass(m,'B');
FOR(i,m){
  int u=comp[edges[i].fi],v=comp[edges[i].se];
  if(u!=v){
    tree[u].pb({v,i});
    tree[v].pb({u,i});
  }
}
dep.ass(tecc.k,0);
upp.ass(LOG,V<int>(tecc.k,-1));
FOR(i,tecc.k){
  if(!dep[i])dfs_lca(i,-1,1);
}
FOR(i,LOG-1){
  FOR(j,tecc.k){
    if(!!~upp[i][j])upp[i+1][j]=upp[i][upp[i][j]];
  }
}
int q;
cin>>q;
diff_up.ass(tecc.k,0);
diff_down.ass(tecc.k,0);
while(q--){
  int x,y;
  cin>>x>>y;
  --x;
  --y;
  int cx=comp[x],cy=comp[y];
  if(cx==cy)continue;
  int anc=get_lca(cx,cy,tecc.k);
  diff_up[cx]++;
  diff_up[anc]--;
  diff_down[cy]++;
  diff_down[anc]--;
}
FOR(i,tecc.k){
  if(dep[i]==1)dfs_solve(i,-1);
}
cout<<res<<'\n';
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
    #ifndef ONLINE_JUDGE
      freopen("output.txt", "w", stdout);
      freopen("input.txt", "r", stdin);
      freopen("Error.txt", "w", stderr);
    #endif

    int tt=1;
    //cin>>tt;
    while(tt--)solve();

    return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:179:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  179 |       freopen("output.txt", "w", stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:180:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  180 |       freopen("input.txt", "r", stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:181:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  181 |       freopen("Error.txt", "w", stderr);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...