oj.uz

Submission #277121

# Submission time Handle Problem Language Result Execution time Memory
277121 2020-08-21T03:48:56 Z tinjyu Duathlon (APIO18_duathlon) C++14
23 / 100
 1000 ms 1048580 KB 
#include <iostream>
using namespace std;
long long int cnt,tag[100005],son[1000005],ans,tmp[1000005],n,m,road[1000005],map[1000005][2];
void dfs(int x,int fa)
{
	tag[x]=1;
	son[x]=1;
	cnt++;
	long long int g=road[x];
	while(g!=-1)
	{
		long long int now=map[g][0];
		if(now!=fa)
		{
			dfs(now,x);
			son[x]+=son[now];
		}
		g=map[g][1];
	}
	return ;
}
void find(int x,int fa)
{
	long long int g=road[x];
	while(g!=-1)
	{
		long long int now=map[g][0];
		if(now!=fa)
		{
			ans+=(cnt-son[now]-1)*son[now];
		}
		g=map[g][1];
	}
	ans+=(cnt-son[x])*(son[x]-1);
	g=road[x];
	while(g!=-1)
	{
		long long int now=map[g][0];
		if(now!=fa)
		{
			find(now,x);
		}
		g=map[g][1];
	}
	return ;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)road[i]=-1;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		map[i*2][0]=v;
		map[i*2][1]=road[u];
		road[u]=i*2;
		map[i*2+1][0]=u;
		map[i*2+1][1]=road[v];
		road[v]=i*2+1;
	}
	for(int i=1;i<=n;i++)
	{
		if(tag[i]==0)
		{
			cnt=0;
			dfs(i,-1);
			find(i,-1);
			//cout<<i<<" "<<ans<<endl;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1112 ms 356100 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 5844 KB Output is correct
2 Correct 133 ms 5972 KB Output is correct
3 Correct 130 ms 6008 KB Output is correct
4 Correct 136 ms 6008 KB Output is correct
5 Correct 137 ms 6008 KB Output is correct
6 Correct 145 ms 8568 KB Output is correct
7 Correct 139 ms 7672 KB Output is correct
8 Correct 135 ms 7288 KB Output is correct
9 Correct 141 ms 6880 KB Output is correct
10 Correct 140 ms 6008 KB Output is correct
11 Correct 132 ms 7120 KB Output is correct
12 Correct 145 ms 7032 KB Output is correct
13 Correct 141 ms 7032 KB Output is correct
14 Correct 139 ms 6648 KB Output is correct
15 Correct 121 ms 6136 KB Output is correct
16 Correct 69 ms 4856 KB Output is correct
17 Correct 132 ms 7124 KB Output is correct
18 Correct 133 ms 7032 KB Output is correct
19 Correct 143 ms 7088 KB Output is correct
20 Correct 138 ms 7168 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Runtime error 644 ms 1048580 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 5752 KB Output is correct
2 Correct 134 ms 5752 KB Output is correct
3 Runtime error 818 ms 1048580 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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