Submission #1221177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221177		LeonidCuk	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	42 ms	15548 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>>g[100000],v;
vector<int>er(100000),low(100000),res(100000),klk(100000),res1(100000);
vector<bool>vis(100000);
int timer=0;
void dfs(int a,int b)
{
    vis[a]=true;
    er[a]=timer;timer++;
    low[a]=er[a];
    bool check=false;
    for(auto p:g[a])
    {
        int i=p.first;
        if(i==b&&!check)
        {
            check=true;continue;
        }
        if(vis[i])
        {
            low[a]=min(low[a],er[i]);
        }
        else
        {
            dfs(i,a);
            low[a]=min(low[a],low[i]);
            if(low[i]>er[a])
            {
                res1[p.second]=1;
                if(klk[i]>0)
                {
                    if(v[p.second].first==a)res[p.second]=1;
                    else res[p.second]=-1;
                }
                else if(klk[i]<0)
                {
                    if(v[p.second].first==a)res[p.second]=-1;
                    else res[p.second]=1;
                }
            }
            klk[a]+=klk[i];
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m,a,b,q;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        cin>>a>>b;
        g[a-1].push_back({b-1,i});
        g[b-1].push_back({a-1,i});
        v.push_back({a-1,b-1});
    }
    cin>>q;
    for(int i=0;i<q;i++)
    {
        cin>>a>>b;
        klk[a-1]++;
        klk[b-1]--;
    }
    for(int i=0;i<n;i++)if(!vis[i])dfs(i,-1);
    for(int i=0;i<m;i++)
    {
        if(res[i]==0)cout<<"B";
        else if(res[i]==1)cout<<"L";
        else cout<<"R";
    }
}

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