oj.uz

Submission #568737

# Submission time Handle Problem Language Result Execution time Memory
568737 2022-05-26T06:48:15 Z inluminas Duathlon (APIO18_duathlon) C++17
23 / 100
 1000 ms 1048576 KB 
#include"bits/stdc++.h"
using namespace std;

#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
#define inf LLONG_MAX
#define l first
#define r second

const ll lmt=2e5+10;
vector<ll>adj[lmt];
bool vis[lmt];
ll c[lmt],par[lmt],sz[lmt];
ll ans=0;
map<pair<ll,ll>,ll>z;

ll findpar(ll p){
	if(par[p]==p) return p;
	return par[p]=findpar(par[p]);
} 

void merge(ll u,ll v){
	u=findpar(u),v=findpar(v);
	par[u]=v;
	sz[v]+=sz[u];
	return;
}

void dfs(ll u,ll p){
 	c[u]=vis[u]=1;
 	ll pu=findpar(u);
 	for(ll v:adj[u]){
 		if(v==p) continue; 
 		dfs(v,u);
 		c[u]+=c[v];
 		z[{u,v}]=c[v];
 		z[{v,u}]=sz[pu]-c[v];
 	}
}

int main(){
	fastio;

	ll n,m;
	cin>>n>>m;
	for(ll i=1;i<=n;i++){
		par[i]=i,sz[i]=1;
	}
	for(ll i=1;i<=m;i++){
		ll u,v;
		cin>>u>>v;
		merge(u,v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	for(ll i=1;i<=n;i++){
		if(vis[i]) continue;
		dfs(i,0);
	}

	for(ll i=1;i<=n;i++){
		ll p=findpar(i);
		for(ll v:adj[i]){
			ll val=z[{i,v}];
			ans+=(val*(sz[p]-val-1));
		}
	}

	cout<<ans<<endl;
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 458 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 458 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1102 ms 802564 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 4 ms 5204 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 4 ms 5332 KB Output is correct
5 Correct 4 ms 5288 KB Output is correct
6 Correct 4 ms 5204 KB Output is correct
7 Correct 5 ms 5204 KB Output is correct
8 Correct 4 ms 5204 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct
10 Correct 4 ms 5204 KB Output is correct
11 Correct 4 ms 5204 KB Output is correct
12 Correct 4 ms 5204 KB Output is correct
13 Correct 6 ms 5204 KB Output is correct
14 Correct 4 ms 5204 KB Output is correct
15 Correct 4 ms 5204 KB Output is correct
16 Correct 3 ms 5076 KB Output is correct
17 Correct 4 ms 5204 KB Output is correct
18 Correct 3 ms 5204 KB Output is correct
19 Correct 3 ms 5204 KB Output is correct
20 Correct 4 ms 5204 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 23964 KB Output is correct
2 Correct 191 ms 24988 KB Output is correct
3 Correct 254 ms 24968 KB Output is correct
4 Correct 189 ms 24928 KB Output is correct
5 Correct 231 ms 24988 KB Output is correct
6 Correct 207 ms 32820 KB Output is correct
7 Correct 182 ms 30760 KB Output is correct
8 Correct 236 ms 29200 KB Output is correct
9 Correct 224 ms 27676 KB Output is correct
10 Correct 192 ms 24976 KB Output is correct
11 Correct 216 ms 24984 KB Output is correct
12 Correct 199 ms 24976 KB Output is correct
13 Correct 214 ms 24976 KB Output is correct
14 Correct 188 ms 23356 KB Output is correct
15 Correct 152 ms 21708 KB Output is correct
16 Correct 77 ms 16764 KB Output is correct
17 Correct 191 ms 25536 KB Output is correct
18 Correct 207 ms 25468 KB Output is correct
19 Correct 181 ms 25356 KB Output is correct
20 Correct 201 ms 25284 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5204 KB Output is correct
2 Correct 4 ms 5160 KB Output is correct
3 Runtime error 600 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 24168 KB Output is correct
2 Correct 187 ms 24856 KB Output is correct
3 Runtime error 776 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 458 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 458 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -