oj.uz

Submission #319743

# Submission time Handle Problem Language Result Execution time Memory
319743 2020-11-06T10:40:10 Z soroush Rigged Roads (NOI19_riggedroads) C++14
100 / 100
 1581 ms 114696 KB 
/*
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7404 KB Output is correct
2 Correct 5 ms 7404 KB Output is correct
3 Correct 5 ms 7404 KB Output is correct

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7404 KB Output is correct
2 Correct 5 ms 7404 KB Output is correct
3 Correct 5 ms 7404 KB Output is correct
4 Correct 6 ms 7660 KB Output is correct
5 Correct 6 ms 7660 KB Output is correct
6 Correct 6 ms 7788 KB Output is correct
7 Correct 6 ms 7532 KB Output is correct
8 Correct 6 ms 7660 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 39180 KB Output is correct
2 Correct 446 ms 50396 KB Output is correct
3 Correct 347 ms 21348 KB Output is correct
4 Correct 696 ms 95056 KB Output is correct
5 Correct 733 ms 99280 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 48644 KB Output is correct
2 Correct 222 ms 23652 KB Output is correct
3 Correct 90 ms 15844 KB Output is correct
4 Correct 224 ms 37940 KB Output is correct
5 Correct 62 ms 20068 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 751 ms 94400 KB Output is correct
2 Correct 812 ms 104152 KB Output is correct
3 Correct 199 ms 34824 KB Output is correct
4 Correct 316 ms 48636 KB Output is correct
5 Correct 988 ms 114696 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 772 ms 65276 KB Output is correct
2 Correct 447 ms 47308 KB Output is correct
3 Correct 1368 ms 101116 KB Output is correct
4 Correct 1328 ms 94672 KB Output is correct
5 Correct 65 ms 16052 KB Output is correct

Subtask #7
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7404 KB Output is correct
2 Correct 5 ms 7404 KB Output is correct
3 Correct 5 ms 7404 KB Output is correct
4 Correct 6 ms 7660 KB Output is correct
5 Correct 6 ms 7660 KB Output is correct
6 Correct 6 ms 7788 KB Output is correct
7 Correct 6 ms 7532 KB Output is correct
8 Correct 6 ms 7660 KB Output is correct
9 Correct 224 ms 39180 KB Output is correct
10 Correct 446 ms 50396 KB Output is correct
11 Correct 347 ms 21348 KB Output is correct
12 Correct 696 ms 95056 KB Output is correct
13 Correct 733 ms 99280 KB Output is correct
14 Correct 325 ms 48644 KB Output is correct
15 Correct 222 ms 23652 KB Output is correct
16 Correct 90 ms 15844 KB Output is correct
17 Correct 224 ms 37940 KB Output is correct
18 Correct 62 ms 20068 KB Output is correct
19 Correct 751 ms 94400 KB Output is correct
20 Correct 812 ms 104152 KB Output is correct
21 Correct 199 ms 34824 KB Output is correct
22 Correct 316 ms 48636 KB Output is correct
23 Correct 988 ms 114696 KB Output is correct
24 Correct 772 ms 65276 KB Output is correct
25 Correct 447 ms 47308 KB Output is correct
26 Correct 1368 ms 101116 KB Output is correct
27 Correct 1328 ms 94672 KB Output is correct
28 Correct 65 ms 16052 KB Output is correct
29 Correct 1581 ms 89024 KB Output is correct
30 Correct 1566 ms 95616 KB Output is correct
31 Correct 1460 ms 96644 KB Output is correct
32 Correct 487 ms 21036 KB Output is correct
33 Correct 1386 ms 97204 KB Output is correct