oj.uz

Submission #408999

# Submission time Handle Problem Language Result Execution time Memory
408999 2021-05-20T03:47:57 Z juggernaut Duathlon (APIO18_duathlon) C++17
0 / 100
 860 ms 1048580 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];
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]){
				is_bridge=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){
	sz[v]=ver_sz[v];
	vis[v]=true;
	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);
	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:79:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
count_triplets.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |   scanf("%d%d",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 ms 5080 KB Output is correct
5 Correct 4 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 4 ms 5068 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 ms 5080 KB Output is correct
5 Correct 4 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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 20268 KB Output is correct
2 Correct 81 ms 20344 KB Output is correct
3 Runtime error 627 ms 1048580 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 658 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 860 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 708 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 647 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 ms 5080 KB Output is correct
5 Correct 4 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 4 ms 5068 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 3 ms 5080 KB Output is correct
5 Correct 4 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 -