oj.uz

Submission #409009

# Submission time Handle Problem Language Result Execution time Memory
409009 2021-05-20T04:41:20 Z juggernaut Duathlon (APIO18_duathlon) C++17
31 / 100
 215 ms 33636 KB 
//Subtask 1
//Subtask 2
//*Subtask 3
//*Subtask 4
//*Subtask 5
//Subtask 6
//Subtask 7
//Subtask 8
//Subtask 9
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
int n,m,timer,tin[100005],fup[100005];
vector<pair<int,bool>>g[100005];
vector<int>gr[100005];
bool vis[100005];
int new_id[100005];
int ver_sz[100005];
int sz[100005];
unordered_map<ll,bool>mp;
vector<pair<int,int>>bridges;
template<class T>void umin(T &a,T b){if(b<a)a=b;}
template<class T>void umax(T &a,T b){if(a<b)a=b;}
void dfs(int v,int p){
	tin[v]=fup[v]=++timer;
	vis[v]=true;
	for(auto &[to,is_bridge]:g[v])if(to!=p){
		if(vis[to])umin(fup[v],tin[to]);
		else{
			dfs(to,v);
			umin(fup[v],fup[to]);
			if(fup[to]>tin[v]){
				mp[(1ll*v)<<32|to]=true;
				mp[(1ll*to)<<32|v]=true;
				bridges.emplace_back(v,to);
			}
		}
	}
}
void enumerate(int v){
	vis[v]=true;
	new_id[v]=timer;
	ver_sz[timer]++;
	for(auto [to,is_bridge]:g[v])if(!is_bridge&&!vis[to])enumerate(to);
}
ll ans=0;
void go(int v,int p){
	vis[v]=true;
	sz[v]=ver_sz[v];
	for(int to:gr[v])if(to!=p){
		go(to,v);
		sz[v]+=sz[to];
	}
}
void calc(int v,int p,int root){
	ll tmp=ver_sz[v];
	//All inside circle
	ans+=tmp*(tmp-1)*(tmp-2);
	vector<ll>vec;
	ll sum=0;
	for(int to:gr[v])if(to!=p){
		vec.push_back(sz[to]);
		sum+=sz[to];
	}
	if(root^v){
		sum+=sz[root]-sz[v];
		vec.push_back(sz[root]-sz[v]);
	}
	//In cirle only center
	for(ll x:vec){
		sum-=x;
		ans+=tmp*x*sum;
		sum+=x;
	}
	//Start or Finish in circle
	ans+=2ll*sum*(tmp-1)*(tmp-1);
	for(int to:gr[v])if(to!=p)calc(to,v,root);
}
int main(){
	scanf("%d%d",&n,&m);
	while(m--){
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].emplace_back(y,0);
		g[y].emplace_back(x,0);
	}
	for(int i=1;i<=n;i++)if(!vis[i])dfs(i,i);
	for(int i=1;i<=n;i++){
		for(auto &[to,flag]:g[i])flag|=mp[(1ll*i)<<32|to];
	}
	memset(vis,0,sizeof vis);
	timer=0;
	for(int i=1;i<=n;i++)if(!vis[i]){
		timer++;
		enumerate(i);
	}
	for(int i=1;i<=n;i++)g[i].clear();
	memset(vis,0,sizeof vis);
	for(auto [x,y]:bridges){
		x=new_id[x];
		y=new_id[y];
		gr[x].push_back(y);
		gr[y].push_back(x);
	}
	for(int i=1;i<=timer;i++)if(!vis[i])go(i,i),calc(i,i,i);
	printf("%lld",ans);
}

Compilation message

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

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 3 ms 5068 KB Output is correct
6 Correct 3 ms 5068 KB Output is correct
7 Incorrect 4 ms 5068 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 162 ms 32580 KB Output is correct
2 Correct 139 ms 32480 KB Output is correct
3 Correct 165 ms 28968 KB Output is correct
4 Correct 151 ms 31856 KB Output is correct
5 Correct 156 ms 26680 KB Output is correct
6 Correct 164 ms 27880 KB Output is correct
7 Correct 170 ms 25896 KB Output is correct
8 Correct 186 ms 27056 KB Output is correct
9 Correct 198 ms 24252 KB Output is correct
10 Correct 175 ms 25256 KB Output is correct
11 Correct 124 ms 19520 KB Output is correct
12 Correct 119 ms 19248 KB Output is correct
13 Correct 109 ms 18924 KB Output is correct
14 Correct 108 ms 18624 KB Output is correct
15 Correct 88 ms 17204 KB Output is correct
16 Correct 83 ms 16884 KB Output is correct
17 Correct 8 ms 6988 KB Output is correct
18 Correct 8 ms 7052 KB Output is correct
19 Correct 8 ms 6988 KB Output is correct
20 Correct 8 ms 7012 KB Output is correct
21 Correct 8 ms 6988 KB Output is correct
22 Correct 8 ms 7052 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5196 KB Output is correct
2 Correct 5 ms 5264 KB Output is correct
3 Correct 4 ms 5196 KB Output is correct
4 Correct 4 ms 5368 KB Output is correct
5 Correct 5 ms 5272 KB Output is correct
6 Correct 4 ms 5324 KB Output is correct
7 Correct 4 ms 5324 KB Output is correct
8 Correct 4 ms 5324 KB Output is correct
9 Correct 5 ms 5324 KB Output is correct
10 Correct 5 ms 5196 KB Output is correct
11 Correct 5 ms 5260 KB Output is correct
12 Correct 5 ms 5268 KB Output is correct
13 Correct 4 ms 5196 KB Output is correct
14 Correct 4 ms 5192 KB Output is correct
15 Correct 4 ms 5196 KB Output is correct
16 Correct 4 ms 5132 KB Output is correct
17 Correct 4 ms 5284 KB Output is correct
18 Correct 5 ms 5268 KB Output is correct
19 Correct 4 ms 5324 KB Output is correct
20 Correct 4 ms 5324 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 23784 KB Output is correct
2 Correct 189 ms 24992 KB Output is correct
3 Correct 177 ms 25056 KB Output is correct
4 Correct 185 ms 25140 KB Output is correct
5 Correct 195 ms 25028 KB Output is correct
6 Correct 192 ms 33636 KB Output is correct
7 Correct 203 ms 31164 KB Output is correct
8 Correct 201 ms 29540 KB Output is correct
9 Correct 197 ms 27972 KB Output is correct
10 Correct 173 ms 24988 KB Output is correct
11 Correct 184 ms 25108 KB Output is correct
12 Correct 192 ms 25124 KB Output is correct
13 Correct 188 ms 25004 KB Output is correct
14 Correct 157 ms 23908 KB Output is correct
15 Correct 131 ms 21236 KB Output is correct
16 Correct 82 ms 17224 KB Output is correct
17 Correct 144 ms 27264 KB Output is correct
18 Correct 157 ms 26740 KB Output is correct
19 Correct 161 ms 26808 KB Output is correct
20 Correct 189 ms 26364 KB Output is correct

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 23708 KB Output is correct
2 Correct 186 ms 25020 KB Output is correct
3 Incorrect 215 ms 24780 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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