Submission #56077

#	Time	Username	Problem	Language	Result	Execution time	Memory
56077		IvanC	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	580 ms	28200 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
 
typedef pair<int,int> ii;
 
const int MAXN = 1e5 + 10;
const int BUCKET = 330; 

vector<int> grafo[MAXN],tree[MAXN],procurar1[MAXN],procurar2[MAXN];
vector<ii> pares;
map<ii,int> cjt;
int low[MAXN],num[MAXN],jafoi[MAXN],dfsNum,compId[MAXN],compAtual;
int e1[MAXN],e2[MAXN],e3[MAXN],e4[MAXN],ehponte[MAXN];
int tipo1[MAXN],tipo2[MAXN],altura[MAXN],liga[MAXN],pai[MAXN],superpai[MAXN],q1[MAXN],q2[MAXN],N,M,K;
 
void dfs_tarjan(int v,int aresta){
  num[v] = ++dfsNum;
  low[v] = dfsNum;
  for(int i : grafo[v]){
    if(i == aresta) continue;
    int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
    if(num[u] == 0){
      dfs_tarjan(u,i);
      if(low[u] > num[v]) ehponte[i] = 1;
      low[v] = min(low[v],low[u]);
    }
    else{
      low[v] = min(low[v],num[u]);
    }
  }
}
 
void dfs_bridge(int v,int aresta){
  jafoi[v] = 1;
  for(int i : grafo[v]){
    if(i == aresta) continue;
    int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
    if(jafoi[u]) continue;
    if(ehponte[i]){
      compAtual++;
      compId[u] = compAtual;
      dfs_bridge(u,i);
    }
    else{
      compId[u] = compId[v];
      dfs_bridge(u,i);
    }
  }
}
 
void dfs1(int v,int p){
  //printf("DFS\n");
  for(int i : tree[v]){
    int u = (e3[i] != v) ? (e3[i]) : (e4[i]);
    if(u == p) continue;
    pai[u] = v;
    liga[u] = i;
    altura[u] = altura[v] + 1;
    dfs1(u,v);
  }
}

void dfs2(int v,int p,int sp){
  superpai[v] = sp;
  if((altura[v] - 1) % BUCKET == 0) sp = v;
  for(int i : tree[v]){
    int u = (e3[i] != v) ? (e3[i]) : (e4[i]);
    if(u == p) continue;
    dfs2(u,v,sp);
  }
}
 
void LCA(int u,int v){
  while(superpai[u] != superpai[v]){
    if(altura[u] >= altura[v]){
      q1[u]++;
      u = superpai[u];
    }
    else{
      q2[v]++;
      v = superpai[v];
    }
  }
  while(u != v){
    //printf("U %d V %d\n",u,v);
    if(altura[u] >= altura[v]){
      //printf("Tipo1 %d %d\n",u,liga[u]);
      tipo1[liga[u]]++;
      u = pai[u];
    }
    else{
      //printf("Tipo2 %d %d\n",v,liga[v]);
      tipo2[liga[v]]++;
      v = pai[v];
    }
  }
}

void processa(int v){
  int d1 = q1[v],d2 = q2[v],alvo = superpai[v];
  while(v != alvo){
    tipo1[liga[v]] += d1;
    tipo2[liga[v]] += d2;
    v = pai[v];
  }
}

int main(){
  scanf("%d %d",&N,&M);
  for(int i = 1;i<=M;i++){
    scanf("%d %d",&e1[i],&e2[i]);
    grafo[e1[i]].push_back(i);
    grafo[e2[i]].push_back(i);
  }
  scanf("%d",&K);
  for(int i = 1;i<=K;i++){
    int u,v;
    scanf("%d %d",&u,&v);
    pares.push_back(ii(u,v));
  }
  for(int i = 1;i<=N;i++){
    if(num[i] != 0) continue;
    dfs_tarjan(i,-1);
    compAtual++;
    compId[i] = compAtual;
    dfs_bridge(i,-1);
  }
  //printf("Pontes\n");
  for(int i = 1;i<=M;i++){
    if(!ehponte[i]) continue;
    e3[i] = compId[e1[i]];
    e4[i] = compId[e2[i]];
    //printf("%d %d %d %d\n",e1[i],e2[i],e3[i],e4[i]);
    tree[e3[i]].push_back(i);
    tree[e4[i]].push_back(i);
  }
 
  for(int  i = 1;i <= compAtual;i++){
    if(altura[i] != 0) continue;
    //printf("DFS1 %d\n",i);
    altura[i] = 1;
    dfs1(i,-1);
    dfs2(i,-1,i);
    //printf("Foi\n");
  }
 
  for(ii davez : pares){
    int u = compId[davez.first],v = compId[davez.second];
    if(u == v) continue;
    LCA(u,v);
  }
 
  for(int i = 1;i<=compAtual;i++) processa(i); 

  for(int i = 1;i<=M;i++){
    if(ehponte[i] == 0){
      printf("B");
    }
    else if(tipo1[i]){
      if(altura[e3[i]] > altura[e4[i]]) printf("R");
      else printf("L");
    }
    else if(tipo2[i]){
      if(altura[e3[i]] < altura[e4[i]]) printf("R");
      else printf("L");
    }
    else{
      printf("B");
    }
  }
  printf("\n");
  return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&N,&M);
   ~~~~~^~~~~~~~~~~~~~~
oneway.cpp:111:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&e1[i],&e2[i]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:115:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&K);
   ~~~~~^~~~~~~~~
oneway.cpp:118:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&u,&v);
     ~~~~~^~~~~~~~~~~~~~~

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