oj.uz

Submission #97064

# Submission time Handle Problem Language Result Execution time Memory
97064 2019-02-13T16:26:33 Z fefe Duathlon (APIO18_duathlon) C++17
8 / 100
 215 ms 29504 KB 
#include<bits/stdc++.h>
#define MAX_N 100005
#define MAX_M 200005
#define pb push_back
#define mp make_pair
#define all(V) (V).begin(),(V).end()
#define reset(V) (V).clear();(V).resize(0);
#define sq(x) ((x)*(x))
#define abs(x) ((x)>0?(x):(-(x)))
#define fi first
#define se second
#define LL_inf (1LL<<60)
#define full_inf 0x7fffffff
#define half_inf 0x3fffffff
#define inf 0x3fffffff
#define MOD 1000000007LL
#define cpx_mod(x) (((LD)(((LL)x.real())%MOD)),((LD)(((LL)x.imag())%MOD)))
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
typedef pair<LL,LL> pil;
typedef pair<LL,string> pls;
typedef complex<LD> Complex;
typedef long double LD;
int n,m,ln,dep[MAX_N],loc[MAX_N],val[MAX_N];
LL ans;
bool vis[MAX_N];
vector<int> E[MAX_N],L,lst[MAX_N];
vector<pii> bcc[MAX_N];
void merge(int x,int y){
	int p,q;
	p=loc[x];
	q=loc[y];
	if(bcc[p].size()<bcc[q].size())	swap(p,q);
	loc[x]=p;
	while(bcc[q].size()){
		bcc[p].pb(bcc[q].back());		
		bcc[q].pop_back();
	}
}
int make_bcc(int x){
	int z=dep[x]-1,k;
	m++;
	loc[x]=ln++;
	bcc[loc[x]].pb({x,0});
	for(int y:E[x]){
		if(dep[y]){
			z=min(z,dep[y]);
			continue;
		}
		dep[y]=dep[x]+1;
		k=make_bcc(y);
		z=min(z,k);
		if(k==dep[x]){
			bcc[loc[y]].pb({x,0});
			L.pb(loc[y]);
			continue;
		}
		merge(x,y);
	}
	return z;
}
int dfs(int x,int y){
	int sum=0;
	vis[x]=true;
	for(pii &p:bcc[x]){
		p.se++;
		if(p.fi==y)	continue;
		for(int q:lst[p.fi]){
			if(vis[q])	continue;
			p.se+=dfs(q,p.fi)-1;
		}
	}
	for(pii p:bcc[x])	sum+=p.se;
	for(pii &p:bcc[x]){
		if(p.fi==y)	p.se=m-sum+1;
		ans+=((LL)(bcc[x].size()-2))*(LL)p.se*((LL)(m-p.se));
		ans+=2*((LL)val[p.fi])*((LL)(p.se-1));
		val[p.fi]+=(p.se-1);
	}
	return sum;
}
int main(){
	int i,x,y;
	scanf("%d %d",&n,&m);
	for(i=0;i<m;i++){
		scanf("%d %d",&x,&y);
		E[x].pb(y);
		E[y].pb(x);
	}
	for(i=1;i<=n;i++){
		if(dep[i])	continue;
		L.clear();
		L.resize(0);
		dep[i]=1;
		m=0;
		make_bcc(i);
		if(m<2)	continue;
		for(int p:L){
			for(pii z:bcc[p]){
				lst[z.fi].pb(p);
			}
		}
		x=bcc[L[0]][0].fi;
		for(int q:lst[x]){
			dfs(q,x);
		}
	}
	
	
	
	for(i=1;i<=n;i++)	dep[i]=0;	//dep --> count node under me
	
	printf("%lld\n",ans);
	return 0;
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
count_triplets.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7552 KB Output is correct
2 Correct 10 ms 7424 KB Output is correct
3 Correct 11 ms 7424 KB Output is correct
4 Correct 10 ms 7424 KB Output is correct
5 Correct 10 ms 7424 KB Output is correct
6 Correct 10 ms 7424 KB Output is correct
7 Incorrect 10 ms 7424 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 161 ms 29400 KB Output is correct
2 Correct 195 ms 29504 KB Output is correct
3 Correct 189 ms 24564 KB Output is correct
4 Correct 164 ms 26984 KB Output is correct
5 Correct 207 ms 23272 KB Output is correct
6 Correct 214 ms 24180 KB Output is correct
7 Correct 210 ms 21496 KB Output is correct
8 Correct 204 ms 22772 KB Output is correct
9 Correct 194 ms 20600 KB Output is correct
10 Correct 200 ms 21496 KB Output is correct
11 Correct 148 ms 19388 KB Output is correct
12 Correct 136 ms 19192 KB Output is correct
13 Correct 145 ms 19092 KB Output is correct
14 Correct 150 ms 18680 KB Output is correct
15 Correct 130 ms 17828 KB Output is correct
16 Correct 103 ms 17528 KB Output is correct
17 Correct 20 ms 11776 KB Output is correct
18 Correct 23 ms 11776 KB Output is correct
19 Correct 20 ms 11768 KB Output is correct
20 Correct 20 ms 11904 KB Output is correct
21 Correct 23 ms 11776 KB Output is correct
22 Correct 19 ms 11648 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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