제출 #878654

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
878654		Muhammad_Aneeq	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	5 ms	9816 KiB

oneway

/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/
#include <iostream>
#include <set>
#include <vector>
#include <map>
using namespace std;
int const N=1e5+10;
multiset<int>nei[N]={},nei1[N]={};
int vis[N]={};
int g=2;
void dfs(int n,int m=-1)
{
  vis[n]=1;
  for (auto i:nei[n])
  {
    if (i==m)
      continue;
    if (!vis[i])
    {
      nei1[n].insert(i);
      dfs(i,n);
    }
    else
      nei1[i].insert(n);
  }
}
void dfs1(int n)
{
  vis[n]=g;
  for (auto i:nei1[n])
  {
    if (vis[i]!=g)
    {
      dfs1(i);
    }
  }
}
inline void solve()
{
  int n,m;
  cin>>n>>m;
  map<pair<int,int>,char>d,ans;
  vector<pair<int,int>>ed;
  while (m--)
  {
    int a,b;
    cin>>a>>b;
    nei[a].insert(b);
    nei[b].insert(a);
    ed.push_back({a,b});
    d[{a,b}]='L';
    d[{b,a}]='R';
  }
  dfs(1);
  int p;
  cin>>p;
  vector<pair<int,int>>q;
  while (p--)
  {
    int a,b;
    cin>>a>>b;
    q.push_back({a,b});
  }
  for (int i=1;i<=n;i++)
  {
    multiset<int>z=nei1[i];
    for (auto j:z)
    {
      nei1[i].erase(nei1[i].find(j));
      nei1[j].insert(i);
      dfs1(1);
      bool w=1;
      for (auto [a,b]:q)
      {
        if (vis[a]==vis[b]&&vis[b]==g)
          continue;
        else
          w=0;
      }
      if (w)
      {
        ans[{i,j}]=ans[{j,i}]='B';
      }
      else
        ans[{i,j}]=ans[{j,i}]=d[{i,j}];
      nei1[i].insert(j);
      nei1[j].erase(nei1[j].find(i));
      g++;
    }
  }
  for (auto i:ed)
    cout<<ans[i];
  cout<<endl;
}
int main()
{
        solve();
}

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