Submission #51828

#	Time	Username	Problem	Language	Result	Execution time	Memory
51828		istlemin	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	2 ms	248 KiB

oneway

#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

class UnionFind {
public:
	vi p;
    vi r;
	UnionFind(ll n){
        p.resize(n);
        r.resize(n,1);
        rep(i,0,n) p[i] = i;
	}

	ll find(ll v){
        return p[v]==v?v:p[v]=find(p[v]);
	}

    void join(ll a,ll b){
        a = find(a); b = find(b);
        if(r[a]>r[b]) p[b] = a;
        else p[a] = b;
        if(r[a]==r[b]) r[b]++;
    }
};

ll n,m,p;
vector<vi> e;
vector<pii> ps;

vi dfsNum;
vi dfsLow;
vector<bool> in;
ll num = 0;

void findBridges(ll v, ll last){
	if(dfsNum[v]!=-1) return;
    dfsLow[v] = dfsNum[v] = num++;
    random_shuffle(all(e[v]));
	rep(i,0,e[v].size()){
		if(e[v][i]==last) continue;
		findBridges(e[v][i],v);
		dfsLow[v] = min(dfsLow[v],dfsLow[e[v][i]]);
	}
}

ll tn;
vector<vi> te;
vi addUp;
vi addDown;
map<pii,bool> isDown;
map<pii,bool> isUp;

class LCA {
public:
    vector<vi> p;
    vi level;

    LCA(ll x){
        p.resize(30,vi(tn));
        level.resize(tn);
        firstP(0,0,0);
        rep(i,1,30)
			rep(j,0,tn)
				p[i][j] = p[i-1][p[i-1][j]];
	}

    void firstP(ll v, ll last, ll l){
		p[0][v] = last;
		level[v] = l;
		rep(i,0,te[v].size()){
			//cout<<v<<" "<<i<<endl;
			if(te[v][i]!=last){
				firstP(te[v][i],v,l+1);
			}
		}
    }

    ll getLca(ll a,ll b){
        if(level[a]<level[b]) swap(a,b);
        for(ll i = 29;i>=0;--i)
            if(level[p[i][a]]>=level[b])
				a = p[i][a];
		if(a==b) return a;
        for(ll i = 29;i>=0;--i)
            if(p[i][a]!=p[i][b]){
				a = p[i][a];
				b = p[i][b];
            }
		assert(a!=b&&p[0][a]==p[0][b]);
		return p[0][a];
    }
};

pii findUpDown(ll v,ll l){
    ll sumUp = addUp[v];
    ll sumDown = addDown[v];
    rep(i,0,te[v].size()){
        if(te[v][i]!=l){
            pii res = findUpDown(te[v][i],v);
            sumUp += res.first;
            sumDown += res.second;
		}
    }
    if(sumUp>0) isUp[{v,l}] = true;
    if(sumDown>0) isDown[{v,l}] = true;
	return {sumUp,sumDown};
}

int main(){
	cin.sync_with_stdio(false);
	cin>>n>>m;
	e.resize(n);
    vector<pii> edgeList;
    map<pii,ll> numEdges;
    rep(i,0,m){
		ll a,b;
		cin>>a>>b;
		--a; --b;
		edgeList.emplace_back(a,b);
		if(a==b) continue;
		e[a].push_back(b);
		e[b].push_back(a);
		numEdges[{min(a,b),max(a,b)}]++;
    }

    dfsNum.resize(n,-1);
    dfsLow.resize(n);
    findBridges(rand()%n,-1);
    set<pii> bridges;
    set<pii> notBridges;
    rep(v,0,n){
        rep(i,0,e[v].size()){
            if(dfsNum[v]<dfsNum[e[v][i]]){
				if(dfsNum[e[v][i]]==dfsLow[e[v][i]]
				&&numEdges[{min(ll(v),e[v][i]),max(ll(v),e[v][i])}]==1){
					bridges.emplace(min(ll(v),e[v][i]),max(ll(v),e[v][i]));
				}else{
					notBridges.emplace(min(ll(v),e[v][i]),max(ll(v),e[v][i]));
				}
			}
        }
    }

	//cout<<endl;
	//rep(i,0,bridges.size())
		//cout<<bridges[i].first+1<<" "<<bridges[i].second+1<<endl;

	UnionFind uf(n);
    trav(edge,notBridges){
		//rep(i,0,n) cout<<uf.find(i)<<" ";
		//cout<<endl;
		//cout<<notBridges[i].first<<"-"<<notBridges[i].second<<endl;
        uf.join(edge.first,edge.second);
    }
    map<ll,vi> mGroups;
    rep(i,0,n) mGroups[uf.find(i)].push_back(i);
    vector<vi> groups;
    vi groupIndex(n);
    trav(g,mGroups){
        rep(i,0,g.second.size()) groupIndex[g.second[i]] = groups.size();
        //cout<<groups.size()<<": "<<g.second.size()<<endl;
        groups.push_back(g.second);
    }

    tn = groups.size();
    te.resize(tn);
    trav(bridge,bridges){
        ll a = groupIndex[bridge.first];
        ll b = groupIndex[bridge.second];
		te[a].push_back(b);
		te[b].push_back(a);
        //cout<<a<<" "<<b<<endl;
    }

	addUp.resize(tn);
    addDown.resize(tn);

    LCA lcaFinder(1);

    cin>>p;
    rep(i,0,p){
		ll a,b;
		cin>>a>>b;
		a = groupIndex[a-1];
		b = groupIndex[b-1];

        addDown[a]++;
        addUp[b]++;

        ll l = lcaFinder.getLca(a,b);
        addDown[l]--;
        addUp[l]--;
    }

    /*rep(i,0,tn) cout<<addUp[i]<<" ";
    cout<<endl;
	rep(i,0,tn) cout<<addDown[i]<<" ";
    cout<<endl;
	*/
    findUpDown(0,0);
	/*
    cout<<"up: "<<endl;
    trav(a,isUp){
		cout<<a.first.first<<" "<<a.first.second<<endl;
    }
    cout<<"down: "<<endl;
    trav(a,isDown){
		cout<<a.first.first<<" "<<a.first.second<<endl;
    }*/

    rep(i,0,m){
        ll a = edgeList[i].first;
        ll b = edgeList[i].second;
        if(a==b||notBridges.find({min(a,b),max(a,b)})!=notBridges.end()){
			cout<<"B";
			continue;
        }

        a = groupIndex[a];
        b = groupIndex[b];

        if(lcaFinder.level[a]<lcaFinder.level[b]){
            assert(!(isUp[{b,a}]&&isDown[{b,a}]));
            if(isUp[{b,a}]) cout<<"R";
            else if(isDown[{b,a}]) cout<<"L";
            else cout<<"B";
        } else {
            assert(!(isUp[{a,b}]&&isDown[{a,b}]));
            if(isUp[{a,b}]) cout<<"L";
            else if(isDown[{a,b}]) cout<<"R";
            else cout<<"B";
        }
    }

    cout<<endl;
}

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