oj.uz

Submission #104956

# Submission time Handle Problem Language Result Execution time Memory
104956 2019-04-10T00:42:13 Z puyu_liao Duathlon (APIO18_duathlon) C++14
23 / 100
 155 ms 17784 KB 
#include<bits/stdc++.h>
#include<stdint.h>
using namespace std;
#define IOS {cin.tie(0);ios_base::sync_with_stdio(false);}
#define N 300005
#define int int64_t
 
vector<int> v[N];
int sz[N];
int ans = 0;
bitset<N> vis,rt;
 
void dfs(int x,int p){
	vis[x] = 1;
	sz[x] = 1;
	for(int i : v[x]) if(i != p){
		if(vis[i]) exit(-1);
		dfs(i,x);
		sz[x] += sz[i];
	}
}
 
void dfs2(int x, int p, int sum) {
	for(int i : v[x]) {
		if(i != p) dfs2(i, x, sum), ans += sz[i] * (sum - sz[i] - 1);
		else ans += (sum - sz[x]) * (sz[x] - 1);
	}
}
 
int32_t main(){
	IOS;
	int n,m,a,b;
	cin >> n >> m;
	for(int i=0;i<m;i++){
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	//if(m!=n-1) return 0;
	for(int i=1;i<=n;i++) if(!vis[i]){
		rt[i] = 1;
		dfs(i,i);
	}
	//for(int i=1;i<=n;i++) cout << sz[i] << '\n';
	for(int i=1;i<=n;i++) if(rt[i]){
		dfs2(i,i,sz[i]);
	}
	cout << ans << '\n';
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 7424 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 7424 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 125 ms 17784 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 12244 KB Output is correct
2 Correct 113 ms 13188 KB Output is correct
3 Correct 120 ms 13176 KB Output is correct
4 Correct 101 ms 13208 KB Output is correct
5 Correct 104 ms 13180 KB Output is correct
6 Correct 150 ms 16092 KB Output is correct
7 Correct 123 ms 15352 KB Output is correct
8 Correct 143 ms 14840 KB Output is correct
9 Correct 155 ms 14200 KB Output is correct
10 Correct 152 ms 13220 KB Output is correct
11 Correct 148 ms 13176 KB Output is correct
12 Correct 147 ms 13176 KB Output is correct
13 Correct 103 ms 13176 KB Output is correct
14 Correct 97 ms 12964 KB Output is correct
15 Correct 85 ms 12536 KB Output is correct
16 Correct 64 ms 11232 KB Output is correct
17 Correct 55 ms 13420 KB Output is correct
18 Correct 51 ms 13416 KB Output is correct
19 Correct 60 ms 13328 KB Output is correct
20 Correct 80 ms 13416 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Runtime error 8 ms 7424 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 12152 KB Output is correct
2 Correct 112 ms 13096 KB Output is correct
3 Runtime error 102 ms 13012 KB Execution failed because the return code was nonzero
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 7424 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 7424 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -