oj.uz

Submission #92515

# Submission time Handle Problem Language Result Execution time Memory
92515 2019-01-03T09:27:03 Z antimirage Duathlon (APIO18_duathlon) C++14
23 / 100
 1000 ms 1049600 KB 
#include <bits/stdc++.h>
 
#define fr first
#define sc second
#define mk make_pair
#define pb emplace_back
#define all(s) s.begin(), s.end()
 
using namespace std;

const int N = 1e5 + 5;

int n, m, x, y, cn;

vector < vector <int> > g;

long long ans, u[N];

void dfs (int v)
{
	u[v] = 1;
	for (auto to : g[v])
	{
		if (u[to]) continue;
		dfs(to);
		u[v] += u[to];
	}
}
void dfs2 (int v, int root, int p = 0)
{
	ans +=( u[root] - u[v]) * (u[v] - 1) * 2;
	
	for (auto to : g[v])
	{
		if (to == p) continue;
		dfs2(to, root, v);
		
		ans += (u[v] - u[to] - 1) * u[to];
	}
}
main() 
{
	cin >> n >> m;
	g.resize(n + 1);
	
	for (int i = 1; i <= m; i++)
	{
		scanf("%d%d", &x, &y);
		g[x].pb(y);
		g[y].pb(x);
	}
	for (int i = 1; i <= n; i++)
	{
		if (u[i]) continue;
		
		dfs(i);		
		dfs2(i, i);
	}
	cout << ans << endl;
}

Compilation message

count_triplets.cpp:41:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() 
      ^
count_triplets.cpp: In function 'int main()':
count_triplets.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 7976 KB Output is correct
2 Correct 68 ms 7912 KB Output is correct
3 Correct 56 ms 7928 KB Output is correct
4 Correct 59 ms 7928 KB Output is correct
5 Correct 59 ms 7928 KB Output is correct
6 Correct 63 ms 12064 KB Output is correct
7 Correct 63 ms 10704 KB Output is correct
8 Correct 87 ms 9976 KB Output is correct
9 Correct 73 ms 9284 KB Output is correct
10 Correct 71 ms 7928 KB Output is correct
11 Correct 67 ms 7928 KB Output is correct
12 Correct 72 ms 7900 KB Output is correct
13 Correct 72 ms 7928 KB Output is correct
14 Correct 58 ms 7800 KB Output is correct
15 Correct 58 ms 7544 KB Output is correct
16 Correct 31 ms 6648 KB Output is correct
17 Correct 38 ms 8304 KB Output is correct
18 Correct 43 ms 8304 KB Output is correct
19 Correct 45 ms 8272 KB Output is correct
20 Correct 42 ms 8312 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Runtime error 916 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 7952 KB Output is correct
2 Correct 75 ms 7972 KB Output is correct
3 Runtime error 960 ms 1049600 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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