oj.uz

Submission #1007755

# Submission time Handle Problem Language Result Execution time Memory
1007755 2024-06-25T12:38:01 Z amirhoseinfar1385 Duathlon (APIO18_duathlon) C++17
0 / 100
 51 ms 32712 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,fn=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 ;
	}
	fn++;
	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()*(fn-sz[u])*(fn-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){
			fn=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 2 ms 15452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 28876 KB Output is correct
2 Correct 34 ms 28844 KB Output is correct
3 Incorrect 35 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 2 ms 15452 KB Output is correct
4 Correct 3 ms 15640 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 15620 KB Output is correct
9 Correct 2 ms 15452 KB Output is correct
10 Incorrect 2 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 45 ms 24748 KB Output is correct
2 Correct 43 ms 24660 KB Output is correct
3 Correct 46 ms 24660 KB Output is correct
4 Correct 39 ms 24656 KB Output is correct
5 Correct 41 ms 24844 KB Output is correct
6 Correct 45 ms 32712 KB Output is correct
7 Correct 42 ms 29908 KB Output is correct
8 Correct 42 ms 28632 KB Output is correct
9 Correct 39 ms 27340 KB Output is correct
10 Incorrect 32 ms 24660 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 3 ms 15452 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 15536 KB Output is correct
11 Correct 2 ms 15448 KB Output is correct
12 Correct 2 ms 15452 KB Output is correct
13 Correct 3 ms 15452 KB Output is correct
14 Correct 2 ms 15452 KB Output is correct
15 Correct 3 ms 15452 KB Output is correct
16 Incorrect 2 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 42 ms 24656 KB Output is correct
2 Correct 44 ms 24960 KB Output is correct
3 Correct 44 ms 24020 KB Output is correct
4 Correct 40 ms 22864 KB Output is correct
5 Correct 34 ms 21732 KB Output is correct
6 Correct 32 ms 21076 KB Output is correct
7 Correct 33 ms 20984 KB Output is correct
8 Correct 34 ms 20480 KB Output is correct
9 Correct 30 ms 20560 KB Output is correct
10 Correct 28 ms 20312 KB Output is correct
11 Correct 27 ms 20060 KB Output is correct
12 Correct 28 ms 20100 KB Output is correct
13 Correct 27 ms 20060 KB Output is correct
14 Correct 27 ms 22268 KB Output is correct
15 Correct 51 ms 29384 KB Output is correct
16 Correct 42 ms 27532 KB Output is correct
17 Correct 48 ms 28152 KB Output is correct
18 Correct 39 ms 26584 KB Output is correct
19 Incorrect 38 ms 22868 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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