Submission #1302098

#TimeUsernameProblemLanguageResultExecution timeMemory
1302098LudisseyOne-Way Streets (CEOI17_oneway)C++20
0 / 100
0 ms332 KiB
#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;
    vector<pair<int,int>> ed(m);
    vector<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,'B');
    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; 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({{getParent(a,1),getParent(b,1)},i});
    }
    int p; cin >> p; 
    for (int i = 0; i < p; i++)
    {
        int a,b; cin >> a >> b; a--; b--;
        val[getParent(a,1)]++;
        val[getParent(b,1)]--;
    }
    for (int i = 0; i < sz(tree_ed[0]); i++)
    {
        if(getParent(tree_ed[0][i].first.first,2)==getParent(tree_ed[0][i].first.second,2)) return -1;
        neigh[tree_ed[0][i].first.first].push_back(tree_ed[0][i].first.second);
        neigh[tree_ed[0][i].first.second].push_back(tree_ed[0][i].first.first);
        unite(tree_ed[0][i].first.second, tree_ed[0][i].first.first,2);
    }
    dfs(0,0,0);
    for (int i = 0; i < sz(tree_ed[0]); i++)
    {
        int a=tree_ed[0][i].first.first, b=tree_ed[0][i].first.second;
        int s;
        if(depth[a]<depth[b]) s=sm[b];
        else s=sm[a];
        if(s==0) continue;
        if((s<0)^(depth[a]<depth[b])) ans[tree_ed[0][i].second]='L';
        else ans[tree_ed[0][i].second]='R';
    }
    for (int i = 0; i < m; i++) cout << ans[i];
    cout << "\n";    
    return 0;
}   
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...