Submission #319743

#	Time	Username	Problem	Language	Result	Execution time	Memory
319743		soroush	Rigged Roads (NOI19_riggedroads)	C++14	100 / 100	1581 ms	114696 KiB

riggedroads

/*
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma,tune=native")
//*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int  ,int > pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn  = 3e5+100;
const ll mod =1e9+7;
const ld PI = acos((ld)-1);

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define migmig ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

int n , m;
pii e[maxn];
int ans[maxn];
int cur = 1;

vector < int > adj[maxn];
map < pii , int > mp;
int par[maxn][30];
int h[maxn];

int Par[maxn];
int sz[maxn];

int getpar(int v){
	return((v == Par[v]) ? v : Par[v] = getpar(Par[v]));
}

void merge(int u , int v){
	u = getpar(u) , v = getpar(v);
	if(u == v)return;
	if(h[u] < h[v])
		swap(u , v);
	sz[v] += sz[u];
	Par[u] = v;
}

void dfs(int v){
    for (auto u : adj[v]){
        if(u!=par[v][0]){
            par[u][0] = v;
            h[u] = h[v]+1;
            dfs(u);
        }
	}
}

int lca(int u , int v){
    if(h[u] > h[v]){
        swap(u , v);
    }
    for (int i = 20 ; i >= 0 ; i --){
        if(par[v][i] and h[par[v][i]]>=h[u]){
            v = par[v][i];
        }
    }
    if(v == u){
        return(v);
    }
    for (int i = 20 ; i >= 0 ; i --){
        if(par[v][i] != par[u][i]){
            v = par[v][i] , u = par[u][i];
        }
    }
    return(par[v][0]);
}

void init(){
	dfs(1);
	h[0] = -1e9;
	for(int i = 1 ; i <= n;  i ++)
		Par[i] = i , sz[i] = 1;
    for (int j = 1; j < 20 ; j ++){
        for (int i = 1 ; i <= n ; i ++){
            par[i][j] = par[par[i][j - 1]][j - 1];
        }
    }
}

int dist(int u , int v){
	return(h[u] + h[v] - 2*h[lca(u, v)]);
}


void connect(int u , int v){
	int lc = lca(u , v);
	vector < int > vec;
	vec.clear();
	while(h[v] > h[lc]){
		if(ans[mp[{v , par[v][0]}]] == 0)
			vec.pb(mp[{v , par[v][0]}]);
		v = par[v][0];
		v = getpar(v);
	}
	while(h[u] > h[lc]){
		if(ans[mp[{u , par[u][0]}]] == 0)
			vec.pb(mp[{u , par[u][0]}]);
		u = par[u][0];
		u = getpar(u);
	}
	sort(vec.begin() , vec.end());
	vec.resize(unique(vec.begin() , vec.end()) - vec.begin());
	for(int v : vec)
		ans[v] = cur++,merge(e[v].first , e[v].second);
}

int32_t main(){
    migmig;
    cin >> n >> m;
    for(int i = 1 ; i <= m ; i ++)
		cin >> e[i].first >> e[i].second;
	for(int i = 1 ; i < n ; i ++){
		int x;
		cin >> x;
		mp[e[x]] = mp[{e[x].second , e[x].first}] = x;
		adj[e[x].first].pb(e[x].second);
		adj[e[x].second].pb(e[x].first);
	}
	init();
	for(int i = 1 ; i <= m ; i ++){
		if(ans[i])continue;
		if(mp.count(e[i])){
			ans[i] = cur++;
		}
		else{
			connect(e[i].first , e[i].second); // tu derakht masireshun ro add kon
			ans[i] = cur++;
		}
	}
	for(int i = 1; i <= m ; i ++)
		cout << ans[i] << ' ';
    return(0);
}

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 9 / 9
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 32 / 32