oj.uz

Submission #287318

# Submission time Handle Problem Language Result Execution time Memory
287318 2020-08-31T15:24:23 Z ScarletS Duathlon (APIO18_duathlon) C++17
23 / 100
 1000 ms 1048580 KB 
#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x).size()
using namespace std;

const int MAXN = 1e5 + 7;
vector<int> edges[MAXN];
ll subTree[MAXN];
bool done[MAXN];
vector<int> cur;
ll ans=0;

void dfs(int c, int p)
{
	done[c]=1;
	cur.push_back(c);
	subTree[c]=1;
	for (int i : edges[c])
		if (i!=p)
		{
			dfs(i,c);
			ans+=(subTree[i]*(subTree[c]-1));
			//cout<<ans<<" "<<i<<" "<<c<<"\n";
			subTree[c]+=subTree[i];
		}
}

int main()
{
	int n,m,u,v;
	cin>>n>>m;
	while (m--)
	{
		cin>>u>>v;
		edges[u].push_back(v);
		edges[v].push_back(u);
	}
	for (int i=1;i<=n;++i)
		if (!done[i])
		{
			cur.clear();
			dfs(i,0);
			//cout<<ans<<"\n";
			for (int j : cur)
				ans+=((subTree[i]-subTree[j])*(subTree[j]-1));
		}
	cout<<(ans<<1);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 766 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 766 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 1067 ms 305892 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 8640 KB Output is correct
2 Correct 167 ms 8696 KB Output is correct
3 Correct 169 ms 8696 KB Output is correct
4 Correct 162 ms 8760 KB Output is correct
5 Correct 171 ms 8696 KB Output is correct
6 Correct 172 ms 12024 KB Output is correct
7 Correct 172 ms 10836 KB Output is correct
8 Correct 185 ms 10100 KB Output is correct
9 Correct 180 ms 9720 KB Output is correct
10 Correct 168 ms 8568 KB Output is correct
11 Correct 164 ms 8696 KB Output is correct
12 Correct 161 ms 8312 KB Output is correct
13 Correct 165 ms 8312 KB Output is correct
14 Correct 147 ms 7792 KB Output is correct
15 Correct 136 ms 7544 KB Output is correct
16 Correct 92 ms 6520 KB Output is correct
17 Correct 139 ms 9068 KB Output is correct
18 Correct 145 ms 8944 KB Output is correct
19 Correct 138 ms 8940 KB Output is correct
20 Correct 146 ms 8948 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Runtime error 942 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 162 ms 8696 KB Output is correct
2 Correct 176 ms 8692 KB Output is correct
3 Execution timed out 1160 ms 999120 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 766 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 766 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -