Submission #216223

#	Time	Username	Problem	Language	Result	Execution time	Memory
216223		peuch	Tropical Garden (IOI11_garden)	C++17	49 / 100	47 ms	16760 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 150010;

int beaulty[MAXN][2];
int ar[2 * MAXN], in[2 * MAXN], dist[2 * MAXN], marc[2 * MAXN];
vector<int> rev[2 * MAXN];
int cycleSize;
int n, p;

void bfs(int ini);
void getCycle();

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{	
	p = P;
	n = N;
	for(int i = 0; i < N; i++){
		ar[2 * i] = -1;
		ar[2 * i + 1] = -1;
	}
	for(int i = 0; i < M; i++){
		if(ar[2 * R[i][0]] == -1) ar[2 * R[i][0]] = i, beaulty[i][0] = 1;
		else if(ar[2 * R[i][0] + 1] == -1) ar[2 * R[i][0] + 1] = i, beaulty[i][0] = 2;
		if(ar[2 * R[i][1]] == -1) ar[2 * R[i][1]] = i, beaulty[i][1] = 1;
		else if(ar[2 * R[i][1] + 1] == -1) ar[2 * R[i][1] + 1] = i, beaulty[i][1] = 2;
	}
	for(int i = 0; i < M; i++){
		// printf("%d -- %d (%d)\n", R[i][0], R[i][1], i);
		// printf("%d -- %d\n", beaulty[i][0], beaulty[i][1]);
		if(beaulty[i][0] == 1 && beaulty[i][1] == 1){
			ar[2 * R[i][0]] = 2 * R[i][1] + 1;
			ar[2 * R[i][1]] = 2 * R[i][0] + 1;
		}
		else if(beaulty[i][0] == 2 && beaulty[i][1] == 1){
			ar[2 * R[i][0] + 1] = 2 * R[i][1] + 1;
			ar[2 * R[i][1]] = 2 * R[i][0];
		}
		else if(beaulty[i][0] == 1 && beaulty[i][1] == 2){
			ar[2 * R[i][0]] = 2 * R[i][1];
			ar[2 * R[i][1] + 1] = 2 * R[i][0] + 1;
		}
		else{
			if(beaulty[i][0] > 0)
				ar[2 * R[i][0] + (beaulty[i][0]) - 1] = 2 * R[i][1];
			if(beaulty[i][1] > 0)
				ar[2 * R[i][1] + (beaulty[i][1]) - 1] = 2 * R[i][0];
		}
	}
	for(int i = 0; i < N; i++){
		if(ar[2 * i] == -1)
			ar[2 * i] = ar[2 * i + 1]; 
		if(ar[2 * i + 1] == -1)
			ar[2 * i + 1] = ar[2 * i];
	}
	for(int i = 0; i < N; i++){
		rev[ar[2 * i]].push_back(2 * i);
		rev[ar[2 * i + 1]].push_back(2 * i + 1);
	}
	for(int i = 0; i < N; i++)
		in[2 * i] = rev[2 * i].size(), in[2 * i + 1] = rev[2 * i + 1].size();
	for(int i = 0; i < N; i++){
		// printf("%d.0 %d.%d\n%d.1 %d.%d\n", i, ar[2 * i] / 2, ar[2 * i] % 2, i, ar[2 * i + 1] / 2, ar[2 * i + 1] % 2);
	}
	getCycle();
	bfs(P);
	// for(int i = 0; i < N; i++){
	// 	printf("%d\n", dist[2 * i]);
	// }
	//printf("\n");
	// printf("%d\n", cycleSize);
	// for(int i = 0; i < 2 * n; i++){
	// 	if(!marc[i]) printf("%d.%d (%d.%d) ", i / 2, i % 2, ar[i] / 2, ar[i] % 2);
	// }
	// printf("\n");
	for(int i = 0; i < Q; i++){
		int ans = 0;
		for(int j = 0; j < N; j++){
			if(dist[2 * j] == -1) continue;
			if(dist[2 * j] <= G[i] && dist[2 * j] % cycleSize == G[i] % cycleSize) ans++;
		}
		answer(ans);
	}
}

void bfs(int ini){
	queue<int> fila;
	for(int i = 0; i < n; i++){
		dist[2 * i] = -1;
		dist[2 * i + 1] = -1;
	}
	dist[2 * ini] = 0;
	dist[2 * ini + 1] = 0;
	fila.push(2 * ini);
	fila.push(2 * ini + 1);
	while(!fila.empty()){
		int cur = fila.front();
		// printf("\t%d.%d\n", cur / 2, cur % 2);
		fila.pop();
		for(int i = 0; i < rev[cur].size(); i++){
			int viz = rev[cur][i];
			if(dist[viz] != -1) continue;
			fila.push(viz);
			dist[viz] = dist[cur] + 1;
		}
	}
}

void getCycle(){
	queue<int> fila;
	for(int i = 0; i < n; i++){
		if(in[2 * i] == 0) fila.push(2 * i);
		if(in[2 * i + 1] == 0) fila.push(2 * i + 1);
	}
	while(!fila.empty()){
		int cur = fila.front();
		marc[cur] = 1;
		fila.pop();
		int viz = ar[cur];
		if(marc[viz]) continue;
		in[viz]--;
		if(in[viz] == 0) fila.push(viz);
	}
	if(marc[2 * p] && marc[2 * p + 1]){
		cycleSize = 10 * MAXN;
		return;
	}
	int cur = (marc[2 * p]) ? 2 * p + 1 : 2 * p;
	while(marc[cur] == 0){
		marc[cur] = 1;
		cycleSize++;
		cur = ar[cur];
	}
}

Compilation message (stderr)

garden.cpp: In function 'void bfs(int)':
garden.cpp:103:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < rev[cur].size(); i++){
                  ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 49 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31