oj.uz

Submission #13479

# Submission time Handle Problem Language Result Execution time Memory
13479 2015-02-21T21:05:48 Z ainta Tropical Garden (IOI11_garden) C++
49 / 100
 133 ms 28704 KB 
#include "garden.h"
#include "gardenlib.h"
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

int deg[150010], Mn[150010], F[300010], D[300010], n, Res[2010];
bool v[300010];
vector<int>E[300010];

void DFS(int a, int d){
	int i;
	D[a] = d;
	for (i = 0; i < E[a].size(); i++){
		if (D[E[a][i]] == -1)DFS(E[a][i], d + 1);
	}
}

int QQ, DD[300010];
struct Query{
	int a, num;
	bool operator<(const Query &p)const{
		return a < p.a;
	}
}w[2010];

int S[300010];

void Do(int a){
	int i, x, c = 0, cnt = 0, pv;
	for (i = 0; i < 2 * n; i++){
		D[i] = -1;
		v[i] = false;
		S[i] = 0;
	}
	DFS(a, 0);
	for (i = 0; i < n; i++){
		if (D[i] != -1){
			DD[cnt++] = D[i];
		}
	}
	sort(DD, DD + cnt);
	x = a;
	while (!v[x]){
		c++;
		v[x] = true;
		x = F[x];
	}
	if (x != a){
		c = 1000000009;
	}
	pv = 0;
	for (i = 0; i < QQ; i++){
		while (pv < cnt && DD[pv] <= w[i].a){
			S[DD[pv] % c]++;
			pv++;
		}
		Res[w[i].num] += S[w[i].a%c];
	}
}

void Add(int a, int b, int i){
	if (Mn[a] == i){
		if (Mn[b] != i || deg[b] == 1)F[a] = b;
		else F[a] = b + n;
	}
	else if (F[a + n] == -1){
		if (Mn[b] != i || deg[b] == 1)F[a + n] = b;
		else F[a + n] = b + n;
	}
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
	int i, a, b;
	n = N;
	QQ = Q;
	for (i = 0; i < Q; i++){
		w[i].a = G[i];
		w[i].num = i;
	}
	sort(w, w + Q);
	for (i = 0; i < 2 * N; i++)F[i] = -1;
	for (i = 0; i < M; i++){
		a = R[i][0], b = R[i][1];
		deg[a]++, deg[b]++;
		if (!Mn[a])Mn[a] = i + 1;
		if (!Mn[b])Mn[b] = i + 1;
	}
	for (i = 0; i < M; i++){
		a = R[i][0], b = R[i][1];
		Add(a, b, i+1);
		Add(b, a, i+1);
	}
	for (i = 0; i < N; i++){
		E[F[i]].push_back(i);
		if (deg[i]>1)E[F[i + N]].push_back(i + N);
	}
	Do(P);
	if (deg[P] != 1)Do(P + N);
	for (i = 0; i < Q; i++)answer(Res[i]);
}

Compilation message

garden.cpp: In function 'void DFS(int, int)':
garden.cpp:15:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < E[a].size(); i++){
              ~~^~~~~~~~~~~~~

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7516 KB Output is correct
2 Correct 9 ms 7516 KB Output is correct
3 Correct 9 ms 7560 KB Output is correct
4 Correct 8 ms 7388 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 9 ms 7544 KB Output is correct
7 Correct 8 ms 7388 KB Output is correct
8 Correct 9 ms 7516 KB Output is correct
9 Correct 14 ms 7700 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7516 KB Output is correct
2 Correct 9 ms 7516 KB Output is correct
3 Correct 9 ms 7560 KB Output is correct
4 Correct 8 ms 7388 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 9 ms 7544 KB Output is correct
7 Correct 8 ms 7388 KB Output is correct
8 Correct 9 ms 7516 KB Output is correct
9 Correct 14 ms 7700 KB Output is correct
10 Correct 8 ms 7352 KB Output is correct
11 Correct 18 ms 9564 KB Output is correct
12 Correct 31 ms 11000 KB Output is correct
13 Correct 69 ms 22740 KB Output is correct
14 Correct 100 ms 18240 KB Output is correct
15 Correct 133 ms 18952 KB Output is correct
16 Correct 113 ms 16112 KB Output is correct
17 Runtime error 85 ms 28704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7516 KB Output is correct
2 Correct 9 ms 7516 KB Output is correct
3 Correct 9 ms 7560 KB Output is correct
4 Correct 8 ms 7388 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Correct 9 ms 7544 KB Output is correct
7 Correct 8 ms 7388 KB Output is correct
8 Correct 9 ms 7516 KB Output is correct
9 Correct 14 ms 7700 KB Output is correct
10 Correct 8 ms 7352 KB Output is correct
11 Correct 18 ms 9564 KB Output is correct
12 Correct 31 ms 11000 KB Output is correct
13 Correct 69 ms 22740 KB Output is correct
14 Correct 100 ms 18240 KB Output is correct
15 Correct 133 ms 18952 KB Output is correct
16 Correct 113 ms 16112 KB Output is correct
17 Runtime error 85 ms 28704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -