oj.uz

Submission #51831

# Submission time Handle Problem Language Result Execution time Memory
51831 2018-06-21T12:40:52 Z istlemin One-Way Streets (CEOI17_oneway) C++14
100 / 100
 1905 ms 113964 KB 
#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;
    vector<bool> lSeen;
    vi level;
	vi roots;
    LCA(ll x){
        p.resize(30,vi(tn));
        lSeen.resize(tn);
        level.resize(tn);
        rep(i,0,tn){
			if(lSeen[i]) continue;
            roots.push_back(i);
			firstP(i,i,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){
		lSeen[v] = true;
		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);
    rep(i,0,n)
		findBridges(i,-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;
	trav(edge,bridges)
		cout<<edge.first+1<<" "<<edge.second+1<<endl;
*/
	UnionFind uf(n);
    trav(edge,notBridges){
		/*rep(i,0,n) cout<<uf.find(i)<<" ";
		cout<<endl;
		cout<<edge.first<<"-"<<edge.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;
*/
	rep(i,0,lcaFinder.roots.size())
		findUpDown(lcaFinder.roots[i],-1);
/*
    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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 5 ms 680 KB Output is correct
4 Correct 5 ms 1384 KB Output is correct
5 Correct 6 ms 1452 KB Output is correct
6 Correct 3 ms 1452 KB Output is correct
7 Correct 5 ms 1520 KB Output is correct
8 Correct 5 ms 1520 KB Output is correct
9 Correct 4 ms 1520 KB Output is correct
10 Correct 3 ms 1520 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 5 ms 680 KB Output is correct
4 Correct 5 ms 1384 KB Output is correct
5 Correct 6 ms 1452 KB Output is correct
6 Correct 3 ms 1452 KB Output is correct
7 Correct 5 ms 1520 KB Output is correct
8 Correct 5 ms 1520 KB Output is correct
9 Correct 4 ms 1520 KB Output is correct
10 Correct 3 ms 1520 KB Output is correct
11 Correct 298 ms 21832 KB Output is correct
12 Correct 317 ms 24712 KB Output is correct
13 Correct 386 ms 30316 KB Output is correct
14 Correct 465 ms 46820 KB Output is correct
15 Correct 605 ms 54928 KB Output is correct
16 Correct 763 ms 92800 KB Output is correct
17 Correct 779 ms 96140 KB Output is correct
18 Correct 764 ms 96140 KB Output is correct
19 Correct 757 ms 99864 KB Output is correct
20 Correct 361 ms 99864 KB Output is correct
21 Correct 292 ms 99864 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 5 ms 680 KB Output is correct
4 Correct 5 ms 1384 KB Output is correct
5 Correct 6 ms 1452 KB Output is correct
6 Correct 3 ms 1452 KB Output is correct
7 Correct 5 ms 1520 KB Output is correct
8 Correct 5 ms 1520 KB Output is correct
9 Correct 4 ms 1520 KB Output is correct
10 Correct 3 ms 1520 KB Output is correct
11 Correct 298 ms 21832 KB Output is correct
12 Correct 317 ms 24712 KB Output is correct
13 Correct 386 ms 30316 KB Output is correct
14 Correct 465 ms 46820 KB Output is correct
15 Correct 605 ms 54928 KB Output is correct
16 Correct 763 ms 92800 KB Output is correct
17 Correct 779 ms 96140 KB Output is correct
18 Correct 764 ms 96140 KB Output is correct
19 Correct 757 ms 99864 KB Output is correct
20 Correct 361 ms 99864 KB Output is correct
21 Correct 292 ms 99864 KB Output is correct
22 Correct 1726 ms 102728 KB Output is correct
23 Correct 1803 ms 102956 KB Output is correct
24 Correct 1897 ms 105548 KB Output is correct
25 Correct 1769 ms 113964 KB Output is correct
26 Correct 1905 ms 113964 KB Output is correct
27 Correct 1902 ms 113964 KB Output is correct
28 Correct 122 ms 113964 KB Output is correct
29 Correct 419 ms 113964 KB Output is correct
30 Correct 344 ms 113964 KB Output is correct
31 Correct 394 ms 113964 KB Output is correct
32 Correct 1041 ms 113964 KB Output is correct