oj.uz

Submission #448699

# Submission time Handle Problem Language Result Execution time Memory
448699 2021-07-31T18:24:11 Z S2speed Pipes (CEOI15_pipes) C++17
100 / 100
 1394 ms 14652 KB 
#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
#define mp(x , y) make_pair(x , y)
#define wall cout<<"--------------------------------------"<<endl
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
typedef pair<pll , ll> plll;
typedef pair<pii , int> piii;
typedef pair<pll , pll> pllll;

const ll maxn = 1e5 + 16 , md = 2000000357 , inf = 2e16;

ll gcd(ll a , ll b){
	if(a < b) swap(a , b);
	if(b == 0) return a;
	return gcd(b , a % b);
}

ll tav(ll n , ll k){
	ll res = 1;
	while(k > 0){
		if(k & 1){
			res *= n; res %= md;
		}
		n *= n; n %= md;
		k >>= 1;
	}
	return res;
}

int ds[maxn][2];

int dsu(int v , bool c){
	return (ds[v][c] == v ? v : ds[v][c] = dsu(ds[v][c] , c));
}

bool merge(int v , int u , bool c){
	v = dsu(v , c); u = dsu(u , c);
	ds[u][c] = v;
	return (v != u);
}

int f[maxn];
vector<int> adj[maxn];
vector<pii> ed;
bitset<maxn> mark;
int jad[maxn][17] , dis[maxn] , dep = 0;

void jDFS(int r , int par){
	mark[r] = true;
	dis[r] = dep++;
	jad[r][0] = par;
	for(int j = 1 ; j < 17 ; j++){
		if(jad[r][j - 1] == -1) break;
		jad[r][j] = jad[jad[r][j - 1]][j - 1];
	}
	for(auto i : adj[r]){
		if(i == par) continue;
		jDFS(i , r);
	}
	dep--;
	return;
}

int find_jad(int v , int d){
	d = dis[v] - d;
	for(int j = 0 ; j < 17 ; j++){
		if(d & (1 << j)){
			v = jad[v][j];
		}
	}
	return v;
}

int lca(int v , int u){
	if(dis[v] > dis[u]) swap(v , u);
	u = find_jad(u , dis[v]);
	if(v == u) return v;
	for(int j = 16 ; j >= 0 ; j--){
		if(jad[v][j] != jad[u][j]){
			v = jad[v][j];
			u = jad[u][j];
		}
	}
	return jad[v][0];
}

void fDFS(int r , int par){
	mark[r] = true;
	for(auto i : adj[r]){
		if(i == par) continue;
		fDFS(i , r);
		f[r] += f[i];
	}
	return;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int n , m;
	cin>>n>>m;
	for(ll i = 0 ; i < n ; i++){
		ds[i][0] = ds[i][1] = i;
	}
	for(int i = 0 ; i < m ; i++){
		int v , u;
		cin>>v>>u; v--; u--;
		if(merge(v , u , 0)){
			adj[v].push_back(u); adj[u].push_back(v);
		} else if(merge(v , u , 1)){
			ed.push_back({v , u});
		}
	}
	for(int i = 0 ; i < n ; i++){
		if(mark[i]) continue;
		jDFS(i , -1);
	}
	for(pii p : ed){
		int v = p.first , u = p.second , l = lca(v , u);
		f[v]++; f[u]++; f[l] -= 2;
	}
	mark.reset();
	for(int i = 0 ; i < n ; i++){
		if(mark[i]) continue;
		fDFS(i , -1);
	}
	for(int i = 0 ; i < n ; i++){
		if(f[i] != 0 || jad[i][0] == -1) continue;
		cout<<i + 1<<' '<<jad[i][0] + 1<<'\n';
	}
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3196 KB Output is correct
2 Correct 6 ms 3148 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 3108 KB Output is correct
2 Correct 118 ms 3088 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 3828 KB Output is correct
2 Correct 239 ms 3832 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 340 ms 5584 KB Output is correct
2 Correct 304 ms 6100 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 11224 KB Output is correct
2 Correct 421 ms 11180 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 711 ms 12360 KB Output is correct
2 Correct 714 ms 12080 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 958 ms 14644 KB Output is correct
2 Correct 892 ms 14648 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1161 ms 14652 KB Output is correct
2 Correct 1126 ms 14648 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1394 ms 14008 KB Output is correct
2 Correct 1391 ms 14360 KB Output is correct