oj.uz

Submission #203730

# Submission time Handle Problem Language Result Execution time Memory
203730 2020-02-22T01:57:44 Z Segtree Duathlon (APIO18_duathlon) C++14
0 / 100
 162 ms 13688 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];
bool vis[N];
ll ans;
ll dp1[N],dp2[N];
void dfs(ll x){
	vis[x]=1;
	ll v1=1,v2=0;
	for(auto y:g[x])if(vis[y]==0){
		dfs(y);
		ans+=v1*dp2[y]+v2*dp1[y];
		v1+=dp1[y],v2+=dp2[y];
	}
	dp1[x]=v1;
	dp2[x]=v2+v1;
}
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);
	}
	ans=0;
	rep(i,n)vis[i]=0;
	rep(i,n){
		if(vis[i]==0){
			dfs(i);
		}
	}
	ans-=n*(n-1)/2;
	ans*=2;
	cout<<ans<<endl;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 8056 KB Output is correct
2 Correct 134 ms 9336 KB Output is correct
3 Correct 132 ms 9336 KB Output is correct
4 Correct 146 ms 9464 KB Output is correct
5 Correct 138 ms 9464 KB Output is correct
6 Correct 142 ms 12152 KB Output is correct
7 Correct 140 ms 11444 KB Output is correct
8 Correct 150 ms 11000 KB Output is correct
9 Correct 140 ms 10360 KB Output is correct
10 Incorrect 141 ms 9336 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 8056 KB Output is correct
2 Correct 145 ms 9208 KB Output is correct
3 Incorrect 162 ms 9976 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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