제출 #985898

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
985898		alexdd	One-Way Streets (CEOI17_oneway)	C++17	60 / 100	3066 ms	17072 KiB

oneway

#include<iostream>
#include<vector>
using namespace std;
const int INF = 1e9;
int n,m,p;
pair<int,int> e[100005];
int xr[100005];
vector<int> con[100005];
vector<int> relatii[100005];
bool visited[100005],visited_init[100005];
int mind[100005][3];///1 - in sus
int depth[100005];
int tin[100005],tout[100005],timer;
char rez[100005];
int parent[100005];
void dfs_init(int nod)
{
    visited_init[nod]=1;
    tin[nod]=++timer;
    for(auto x:con[nod])
    {
        int adj = nod ^ xr[x];
        if(!visited_init[adj])
        {
            parent[adj]=nod;
            dfs_init(adj);
        }
    }
    tout[nod]=++timer;
}
bool isanc(int x, int y)
{
    if(tin[x]<=tin[y] && tout[x]>=tout[y])
        return 1;
    return 0;
}
void dfs(int nod, int par)
{
    visited[nod]=1;
    mind[nod][0]=mind[nod][1]=mind[nod][2]=INF;
    for(auto x:con[nod])
    {
        if(x==par)
            continue;
        int adj = nod ^ xr[x];
        if(!visited[adj])
        {
            depth[adj] = depth[nod]+1;
            dfs(adj,x);
            for(int i=0;i<3;i++) mind[nod][i] = min(mind[nod][i], mind[adj][i]);
        }
        else
        {
            rez[x] = 'B';
            mind[nod][0] = min(mind[nod][0], depth[adj]);
        }
    }
    for(auto x:relatii[nod])
    {
        if(x<0)
        {
            x = -x;
            mind[nod][2] = min(mind[nod][2], depth[x]);
        }
        else
        {
            mind[nod][1] = min(mind[nod][1], depth[x]);
        }
    }
    if(par==0)
        return;
    if(mind[nod][0] < depth[nod])
    {
        rez[par] = 'B';
    }
    else///bridge
    {

        if(mind[nod][1] >= depth[nod] && mind[nod][2] >= depth[nod])
            rez[par] = 'B';
        else
        {
            if(e[par].first==nod)
            {
                if(mind[nod][1] >= depth[nod]) rez[par] = 'R';
                else rez[par] = 'L';
            }
            else
            {
                if(mind[nod][1] >= depth[nod]) rez[par] = 'L';
                else rez[par] = 'R';
            }
        }
        //rez[par]='X';
    }
}
int lca(int x, int y)
{
    if(isanc(x,y))
        return x;
    if(isanc(y,x))
        return y;
    while(!isanc(x,y))
        x=parent[x];
    return x;
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    int a,b;
    for(int i=1;i<=m;i++)
    {
        cin>>e[i].first>>e[i].second;
        con[e[i].first].push_back(i);
        con[e[i].second].push_back(i);
        xr[i] = e[i].first ^ e[i].second;
    }
    for(int i=1;i<=n;i++)
        if(!visited_init[i])
            dfs_init(i);
    cin>>p;
    for(int i=1;i<=p;i++)
    {
        cin>>a>>b;
        int lc = lca(a,b);
        relatii[a].push_back(-lc);
        relatii[b].push_back(lc);
    }
    for(int i=1;i<=n;i++)
        if(!visited[i])
            dfs(i,0);
    for(int i=1;i<=m;i++)
        cout<<rez[i];
    return 0;
}

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