oj.uz

Submission #448695

# Submission time Handle Problem Language Result Execution time Memory
448695 2021-07-31T17:53:57 Z S2speed Pipes (CEOI15_pipes) C++17
100 / 100
 1476 ms 9288 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;
}

ll ds[maxn];

ll dsu(ll v){
	return (ds[v] == v ? v : ds[v] = dsu(ds[v]));
}

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

ll f[maxn] , par[maxn];
vector<ll> adj[maxn];
bitset<maxn> mark;
int jad[maxn][17];

void fDFS(ll r){
	mark[r] = true;
	for(auto i : adj[r]){
		if(i == par[r]) continue;
		par[i] = r;
		fDFS(i);
		f[r] += f[i];
	}
	f[r] %= md; if(f[r] < 0) f[r] += md;
	return;
}

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

	ll n , m , cur;
	cin>>n>>m;
	iota(ds , ds + n , 0);
	for(ll i = 0 ; i < m ; i++){
		ll v , u;
		cin>>v>>u; v--; u--;
		if(merge(v , u)){
			adj[v].push_back(u); adj[u].push_back(v);
		} else {
			f[v] += cur; f[u] -= cur;
			cur <<= 1; if(cur >= md) cur -= md;
		}
	}
	for(ll i = 0 ; i < n ; i++){
		if(mark[i]) continue;
		par[i] = -1;
		fDFS(i);
	}
	for(ll i = 0 ; i < n ; i++){
		if(f[i] != 0 || par[i] == -1) continue;
		cout<<i + 1<<' '<<par[i] + 1<<'\n';
	}
	return 0;
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:81:8: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
   81 |    cur <<= 1; if(cur >= md) cur -= md;
      |    ~~~~^~~~~

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 5 ms 2892 KB Output is correct
2 Correct 5 ms 3020 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 2852 KB Output is correct
2 Correct 118 ms 3228 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 3176 KB Output is correct
2 Correct 233 ms 3588 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 4028 KB Output is correct
2 Correct 297 ms 4900 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 6796 KB Output is correct
2 Correct 398 ms 6868 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 7472 KB Output is correct
2 Correct 716 ms 8088 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 903 ms 8560 KB Output is correct
2 Correct 846 ms 9288 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1110 ms 8564 KB Output is correct
2 Correct 1075 ms 9240 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1476 ms 8180 KB Output is correct
2 Correct 1365 ms 8768 KB Output is correct