Submission #1078677

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078677		LmaoLmao	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	2 ms	3160 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ii=pair<int,int>;

vector<array<int,3>> bridge;
int timer=0;
int num[100005],low[100005];
vector<ii> adj[100005];
vector<ii> edge;
char ans[100005];
map<ii,bool> cb;
vector<array<int,3>> change;

void dfs(int u,int pre) {
    timer++;
    num[u]=timer;
    low[u]=num[u];
    for(ii v:adj[u]) {
        //cout << v.first <<  endl;
        if(v.first==pre) continue;
        if(!num[v.first] ) {
            dfs(v.first,u);
            low[u]=min(low[u],low[v.first]);
            if(low[v.first]==num[v.first]) {
                bridge.push_back({u,v.first,v.second});
                cb[{u,v.first}]=1;
                cb[{v.first,u}]=1;
            }
        }
        else {
            low[u]=min(low[u],num[v.first]);
        }
    }
    return;
}

int d[100005];

void bfs(int s,int t) {
    for(int i=1;i<=100000;i++) d[i]=0;
    d[s]=1;
    queue<int> q;
    q.push(s);
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        for(ii v:adj[u]) {
            if(d[v.first]==0) {
                d[v.first]=d[u]+1;
                q.push(v.first);
            }
        }
    }
    int k=t;
    while(k!=s) {
        for(ii v:adj[k]) {
            if(d[v.first]==d[k]-1) {
                //cout << k << ' ' << v.first << endl;
                if(cb[{k,v.first}]) change.push_back({v.first,k,v.second});
                k=v.first;
                break;
            }
        }
    }
    return;
}

int main()
{
    int n,m;
    cin >> n >> m;
    edge.push_back({0,0});
    for(int i=1;i<=m;i++) {
        int x,y;
        cin >> x >> y;
        adj[x].push_back({y,i});
        adj[y].push_back({x,i});
        edge.push_back({x,y});
        ans[i]='B';
    }
    dfs(1,0);
    int k;
    cin >> k;
    for(int i=0;i<k;i++) {
        int x,y;
        cin >> x >> y;
        bfs(x,y);
    }
    for(array<int,3> e:change) {
        int u=e[0];
        int v=e[1];
        if(u==edge[e[2]].first && v==edge[e[2]].second) {
            ans[e[2]]='R';
        }
        else {
            ans[e[2]]='L';
        }
    }
    map<ii,int> mp;
    for(int i=1;i<=m;i++) {
        cout << ans[i];
    }
}

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