Submission #1294348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294348		Ludissey	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	1 ms	332 KiB

oneway

#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
using namespace std;
int n,m,p;
vector<int> val;
vector<int> sm;
vector<int> depth;

vector<vector<int>> parent;
vector<vector<int>> sz;
vector<vector<int>> neigh;

int getParent(int x, int k){
    if(parent[x][k]==x) return x;
    return parent[x][k]=getParent(parent[x][k],k);
}

void unite(int a, int b, int k){
    a=getParent(a,k);
    b=getParent(b,k);
    if(a==b) return;
    if(sz[a][k]<sz[b][k]) swap(a,b);
    sz[a][k]+=sz[b][k];
    parent[b][k]=a;
}

int dfs(int x, int p, int d){
    sm[x]=val[x];
    depth[x]=d;
    for (auto u : neigh[x])
    {
        if(u==p) continue;
        sm[x]+=dfs(u,x,d+1);
    }
    return sm[x];
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m >> p;
    vector<pair<int,int>> ed(m);
    vector<pair<pair<int,int>,int>> tree_ed[2];
    parent.resize(n,vector<int>(3,0));
    sz.resize(n,vector<int>(3,1));
    vector<char> ans(m);
    val.resize(n,0);
    neigh.resize(n);
    sm.resize(n,0);   
    depth.resize(n,0);   
    for (int i = 0; i < n; i++) parent[i][0]=parent[i][1]=parent[i][2]=i;
    for (int i = 0; i < m; i++)
    {
        int a,b; cin >> a >> b;
        ed[i]={a,b};
        if(getParent(a,0)==getParent(b,0)) unite(a,b,1);
        else unite(a,b,0);
    }
    for (int i = 0; i < m; i++)
    {
        int a=ed[i].first,b=ed[i].second;
        if(getParent(a,1)!=getParent(b,1)) tree_ed[0].push_back({{a,b},i});
        else tree_ed[1].push_back({{a,b},i}), ans[i]='B';
    }
    for (int i = 0; i < p; i++)
    {
        int a,b; cin >> a >> b; 
        val[a]++;
        val[b]--;
    }
    for (int k=0; k < 2; k++){
        for (int i = 0; i < sz(tree_ed[k]); i++)
        {
            if(getParent(tree_ed[k][i].first.first,2)==getParent(tree_ed[k][i].first.second,2)) continue;
            neigh[tree_ed[k][i].first.first].push_back(tree_ed[k][i].first.second);
            neigh[tree_ed[k][i].first.second].push_back(tree_ed[k][i].first.first);
            unite(tree_ed[k][i].first.second, tree_ed[k][i].first.first,2);
        }
    }
    dfs(0,0,0);
    for (int i = 0; i < sz(tree_ed[0]); i++)
    {
        int a=tree_ed[0][0].first.first, b=tree_ed[0][0].first.second;
        if(val[a]==0) continue;
        if((val[a]<0)^(depth[a]<depth[b])) ans[tree_ed[0][0].second]='L';
        else ans[tree_ed[0][0].second]='R';
    }
    for (int i = 0; i < m; i++) cout << ans[i];
    cout << "\n";    
    return 0;
}   

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