oj.uz

Submission #1007751

# Submission time Handle Problem Language Result Execution time Memory
1007751 2024-06-25T12:35:28 Z amirhoseinfar1385 Duathlon (APIO18_duathlon) C++17
0 / 100
 52 ms 32588 KB 
#include<bits/stdc++.h>
using namespace std;
const long long maxn=200000+10;
vector<long long>adj[maxn],fakeadj[maxn],unnow;
long long n,m,vis[maxn],high[maxn],sz[maxn],newnode,low[maxn],wh[maxn],timea;
long long mainres=0;

void vorod(){
	cin>>n>>m;
	for(long long i=0;i<m;i++){
		long long u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
}

void predfs(long long u){
	if(vis[u]==1){
		return ;
	}
	vis[u]=1;
	timea++;
	wh[u]=low[u]=timea;
	unnow.push_back(u);
	for(auto x:adj[u]){
		if(vis[x]){
			low[u]=min(low[u],wh[x]);
		}else{
			predfs(x);
			low[u]=min(low[u],low[x]);
			if(low[x]>=wh[u]){
			//	cout<<"wtf: "<<u<<" "<<x<<endl;
				fakeadj[u].push_back(newnode);
				while((long long)fakeadj[newnode].size()==0||fakeadj[newnode].back()!=x){
					fakeadj[newnode].push_back(unnow.back());
					unnow.pop_back();
				}
				newnode++;
			}
		}
	}
	//cout<<"magemishe: "<<u<<" "<<wh[u]<<" "<<low[u]<<endl;
}
void dfssolve(long long u){
	vis[u]=1;
	sz[u]=(u<=n);
	for(auto x:fakeadj[u]){
		dfssolve(x);
		sz[u]+=sz[x];
		if(u>n){
			mainres-=sz[x]*(sz[x]-1)*((long long)fakeadj[u].size());
		}
	}
	if(u>n){
		mainres-=(long long)fakeadj[u].size()*(n-sz[u])*(n-sz[u]-1);
	}
	//cout<<u<<" "<<sz[u]<<" "<<(long long)fakeadj[u].size()<<endl;
}

void pre(){
	newnode=n+1;
	for(long long i=1;i<=n;i++){
		if(vis[i]==0){
			predfs(i);
			dfssolve(i);
		}
	}
	for(long long i=1;i<=n;i++){
		vis[i]=0;
	}
}



void solve(){
	mainres+=n*(n-1)*(n-2);
	/*for(long long i=1;i<=n;i++){
		if(vis[i]==0){
			dfssolve(i);
		}
	}*/
	cout<<mainres<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	vorod();
	pre();
	solve();
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 28868 KB Output is correct
2 Correct 33 ms 28868 KB Output is correct
3 Incorrect 44 ms 27728 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 24660 KB Output is correct
2 Correct 35 ms 24656 KB Output is correct
3 Correct 44 ms 24608 KB Output is correct
4 Correct 37 ms 24724 KB Output is correct
5 Correct 37 ms 24812 KB Output is correct
6 Correct 42 ms 32588 KB Output is correct
7 Correct 39 ms 29764 KB Output is correct
8 Correct 36 ms 28436 KB Output is correct
9 Correct 44 ms 27196 KB Output is correct
10 Incorrect 38 ms 24812 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 15452 KB Output is correct
2 Correct 2 ms 15544 KB Output is correct
3 Correct 2 ms 15452 KB Output is correct
4 Correct 2 ms 15452 KB Output is correct
5 Correct 2 ms 15452 KB Output is correct
6 Correct 2 ms 15452 KB Output is correct
7 Correct 2 ms 15452 KB Output is correct
8 Correct 2 ms 15452 KB Output is correct
9 Correct 2 ms 15452 KB Output is correct
10 Correct 2 ms 15448 KB Output is correct
11 Correct 2 ms 15452 KB Output is correct
12 Correct 2 ms 15452 KB Output is correct
13 Correct 2 ms 15452 KB Output is correct
14 Correct 2 ms 15608 KB Output is correct
15 Correct 2 ms 15448 KB Output is correct
16 Incorrect 3 ms 15452 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 24840 KB Output is correct
2 Correct 41 ms 24820 KB Output is correct
3 Correct 42 ms 24272 KB Output is correct
4 Correct 42 ms 23120 KB Output is correct
5 Correct 42 ms 21848 KB Output is correct
6 Correct 36 ms 21072 KB Output is correct
7 Correct 32 ms 20816 KB Output is correct
8 Correct 33 ms 20572 KB Output is correct
9 Correct 29 ms 20560 KB Output is correct
10 Correct 29 ms 20316 KB Output is correct
11 Correct 31 ms 20180 KB Output is correct
12 Correct 35 ms 20360 KB Output is correct
13 Correct 28 ms 20048 KB Output is correct
14 Correct 29 ms 22216 KB Output is correct
15 Correct 52 ms 29388 KB Output is correct
16 Correct 43 ms 27636 KB Output is correct
17 Correct 43 ms 28104 KB Output is correct
18 Correct 49 ms 26576 KB Output is correct
19 Incorrect 39 ms 23116 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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