oj.uz

Submission #203728

# Submission time Handle Problem Language Result Execution time Memory
203728 2020-02-22T01:49:54 Z Segtree Duathlon (APIO18_duathlon) C++14
8 / 100
 145 ms 10232 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define N 100010
ll n,m;
vector<ll> g[N];
ll vcnt,ecnt;
bool vis[N];
void dfs(ll x){
	if(vis[x])return;
	vis[x]=1; vcnt++;
	for(auto y:g[x]){
		ecnt++;
		dfs(y);
	}
}
int main(){
	ll n,m; cin>>n>>m;
	rep(i,m){
		ll a,b; cin>>a>>b;
		a--,b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	ll ans=0;
	rep(i,n)vis[i]=0;
	rep(i,n){
		if(vis[i]==0){
			vcnt=ecnt=0;
			dfs(i);
			ecnt/=2;
			if(ecnt==vcnt-1)ans+=vcnt*(vcnt-1)*(vcnt-2)/3;
			else ans+=vcnt*(vcnt-1)*(vcnt-2);
		}
	}
	cout<<ans<<endl;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 6 ms 2680 KB Output is correct
3 Correct 6 ms 2680 KB Output is correct
4 Correct 6 ms 2680 KB Output is correct
5 Correct 6 ms 2680 KB Output is correct
6 Correct 7 ms 2680 KB Output is correct
7 Incorrect 6 ms 2680 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 6 ms 2680 KB Output is correct
3 Correct 6 ms 2680 KB Output is correct
4 Correct 6 ms 2680 KB Output is correct
5 Correct 6 ms 2680 KB Output is correct
6 Correct 7 ms 2680 KB Output is correct
7 Incorrect 6 ms 2680 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 10232 KB Output is correct
2 Correct 139 ms 10232 KB Output is correct
3 Correct 145 ms 8752 KB Output is correct
4 Correct 145 ms 9492 KB Output is correct
5 Correct 135 ms 8184 KB Output is correct
6 Correct 139 ms 8184 KB Output is correct
7 Correct 145 ms 7796 KB Output is correct
8 Correct 138 ms 8056 KB Output is correct
9 Correct 137 ms 7388 KB Output is correct
10 Correct 135 ms 7672 KB Output is correct
11 Correct 121 ms 7032 KB Output is correct
12 Correct 112 ms 6776 KB Output is correct
13 Correct 103 ms 6776 KB Output is correct
14 Correct 99 ms 6520 KB Output is correct
15 Correct 75 ms 6008 KB Output is correct
16 Correct 78 ms 6008 KB Output is correct
17 Correct 7 ms 2812 KB Output is correct
18 Correct 7 ms 2808 KB Output is correct
19 Correct 7 ms 2808 KB Output is correct
20 Correct 7 ms 2808 KB Output is correct
21 Correct 7 ms 2808 KB Output is correct
22 Correct 7 ms 2808 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 144 ms 7672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 2680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 142 ms 7672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 6 ms 2680 KB Output is correct
3 Correct 6 ms 2680 KB Output is correct
4 Correct 6 ms 2680 KB Output is correct
5 Correct 6 ms 2680 KB Output is correct
6 Correct 7 ms 2680 KB Output is correct
7 Incorrect 6 ms 2680 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 6 ms 2680 KB Output is correct
3 Correct 6 ms 2680 KB Output is correct
4 Correct 6 ms 2680 KB Output is correct
5 Correct 6 ms 2680 KB Output is correct
6 Correct 7 ms 2680 KB Output is correct
7 Incorrect 6 ms 2680 KB Output isn't correct
8 Halted 0 ms 0 KB -