oj.uz

Submission #13478

# Submission time Handle Problem Language Result Execution time Memory
13478 2015-02-21T21:01:12 Z ainta Tropical Garden (IOI11_garden) C++
0 / 100
 9 ms 7544 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]){
		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 < 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
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7544 KB Output is correct
2 Correct 9 ms 7544 KB Output is correct
3 Correct 9 ms 7540 KB Output is correct
4 Correct 8 ms 7392 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Incorrect 9 ms 7544 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7544 KB Output is correct
2 Correct 9 ms 7544 KB Output is correct
3 Correct 9 ms 7540 KB Output is correct
4 Correct 8 ms 7392 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Incorrect 9 ms 7544 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7544 KB Output is correct
2 Correct 9 ms 7544 KB Output is correct
3 Correct 9 ms 7540 KB Output is correct
4 Correct 8 ms 7392 KB Output is correct
5 Correct 8 ms 7416 KB Output is correct
6 Incorrect 9 ms 7544 KB Output isn't correct
7 Halted 0 ms 0 KB -