oj.uz

Submission #103726

# Submission time Handle Problem Language Result Execution time Memory
103726 2019-04-02T09:16:34 Z autumn_eel Duathlon (APIO18_duathlon) C++14
31 / 100
 425 ms 32400 KB 
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

struct BCC{
	int n;
	vector<vector<int>>E;
	vector<bool>used;
	vector<int>dep,low,cmp,cnt;
	set<P>bridge;
	vector<P>es;

	void dfs(int v,int p,int d){
		used[v]=true;
		low[v]=dep[v]=d;
		for(int u:E[v]){
			if(u==p)continue;
			if(used[u]){
				low[v]=min(low[v],dep[u]);
				continue;
			}
			dfs(u,v,d+1);
			if(dep[v]<low[u]){
				bridge.insert(P(min(v,u),max(v,u)));
			}
			low[v]=min(low[v],low[u]);
		}
	}
	void dfs2(int v,int k){
		cmp[v]=k;
		cnt[k]++;
		for(int u:E[v]){
			if(bridge.count(P(min(u,v),max(u,v)))||cmp[u]!=-1)continue;
			dfs2(u,k);
		}
	}
	BCC(vector<vector<int>>E):E(E){
		n=E.size();
		used=vector<bool>(n);
		dep=low=vector<int>(n);
		cmp=vector<int>(n,-1);
		rep(i,n){
			if(!used[i])dfs(i,-1,0);
		}
		int c=0;
		rep(i,n){
			if(cmp[i]==-1){
				cnt.push_back(0);
				dfs2(i,c++);
			}
		}
		for(auto p:bridge){
			es.push_back(P(cmp[p.first],cmp[p.second]));
		}
	}
	vector<int>getvs(){
		return cnt;
	}
	vector<P>getes(){
		return es;
	}
};

int n,m;
vector<int>E[200000];
int sz[200000];
bool used1[200000],used2[200000];
vector<int>vs;

ll ans=0;
int cnt=0;

void dfs1(int v){
	cnt+=vs[v];
	used1[v]=true;
	for(int u:E[v]){
		if(used1[u])continue;
		dfs1(u);
	}
}
void dfs2(int v,int p){
	used2[v]=true;
	int s=cnt-vs[v];
	sz[v]=vs[v];
	for(int u:E[v]){
		if(used2[u])continue;
		dfs2(u,v);
		sz[v]+=sz[u];
		s-=sz[u];
		ans+=sz[u]*(ll)(cnt-sz[u]-vs[v]);
	}
	ans+=s*(ll)(cnt-s-vs[v]);
	if(vs[v]>1){
		ans+=(ll)(cnt-vs[v])*(vs[v]-1)*(vs[v]-1)*2;
	}
}
int main(){
	scanf("%d%d",&n,&m);
	vector<vector<int>>G(n);
	rep(i,m){
		int a,b;scanf("%d%d",&a,&b);a--;b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	BCC bcc(G);
	vs=bcc.getvs();
	auto res=bcc.getes();
	for(auto p:res){
		E[p.first].push_back(p.second);
		E[p.second].push_back(p.first);
	}
	for(int i:vs){
		if(i>=3){
			ans+=i*(ll)(i-1)*(ll)(i-2);
		}
	}
	rep(i,n){
		if(!used1[i]){
			cnt=0;
			dfs1(i);
			dfs2(i,-1);
		}
	}
	cout<<ans<<endl;
}

Compilation message

count_triplets.cpp: In function 'int main()':
count_triplets.cpp:100: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:103:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a,b;scanf("%d%d",&a,&b);a--;b--;
           ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 7 ms 5068 KB Output is correct
5 Correct 6 ms 4992 KB Output is correct
6 Correct 6 ms 4992 KB Output is correct
7 Incorrect 6 ms 4992 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 170 ms 28892 KB Output is correct
2 Correct 176 ms 28956 KB Output is correct
3 Correct 263 ms 29044 KB Output is correct
4 Correct 251 ms 30328 KB Output is correct
5 Correct 292 ms 28404 KB Output is correct
6 Correct 287 ms 29428 KB Output is correct
7 Correct 303 ms 28916 KB Output is correct
8 Correct 274 ms 29428 KB Output is correct
9 Correct 305 ms 28144 KB Output is correct
10 Correct 262 ms 28272 KB Output is correct
11 Correct 215 ms 26356 KB Output is correct
12 Correct 221 ms 26100 KB Output is correct
13 Correct 213 ms 26124 KB Output is correct
14 Correct 179 ms 25556 KB Output is correct
15 Correct 138 ms 24304 KB Output is correct
16 Correct 144 ms 23660 KB Output is correct
17 Correct 23 ms 13952 KB Output is correct
18 Correct 17 ms 13952 KB Output is correct
19 Correct 17 ms 13948 KB Output is correct
20 Correct 19 ms 13948 KB Output is correct
21 Correct 19 ms 13948 KB Output is correct
22 Correct 18 ms 13948 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 29036 KB Output is correct
2 Correct 372 ms 29336 KB Output is correct
3 Correct 328 ms 29172 KB Output is correct
4 Correct 340 ms 29368 KB Output is correct
5 Correct 370 ms 29376 KB Output is correct
6 Correct 400 ms 32400 KB Output is correct
7 Correct 425 ms 31352 KB Output is correct
8 Correct 362 ms 30844 KB Output is correct
9 Correct 341 ms 30164 KB Output is correct
10 Correct 342 ms 29252 KB Output is correct
11 Correct 310 ms 29172 KB Output is correct
12 Correct 291 ms 29172 KB Output is correct
13 Correct 357 ms 29220 KB Output is correct
14 Correct 301 ms 28596 KB Output is correct
15 Correct 245 ms 27764 KB Output is correct
16 Correct 148 ms 23920 KB Output is correct
17 Correct 275 ms 30156 KB Output is correct
18 Correct 256 ms 30188 KB Output is correct
19 Correct 300 ms 30248 KB Output is correct
20 Correct 250 ms 30196 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 29044 KB Output is correct
2 Correct 376 ms 29240 KB Output is correct
3 Incorrect 314 ms 27620 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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