Submission #216231

#	Time	Username	Problem	Language	Result	Execution time	Memory
216231		peuch	Tropical Garden (IOI11_garden)	C++17	49 / 100	50 ms	18808 KiB

garden

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

const int MAXN = 150010;
const int INF = 2000000000;

int beaulty[MAXN][2];
int ar[2 * MAXN], in[2 * MAXN], dist[2][2 * MAXN], marc[2 * MAXN], mod[2][2 * MAXN];
vector<int> rev[2 * MAXN];
int cycleSize[2];
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();
	getCycle();
	bfs(P);
	// for(int i = 0; i < N; i++){
	// 	printf("%d %d\n", dist[0][2 * i], dist[1][2 * i]);
	// }
	for(int i = 0; i < Q; i++){
		int ans = 0;
		for(int j = 0; j < N; j++){
			if(dist[0][2 * j] != -1)
				if(dist[0][2 * j] <= G[i] && dist[0][2 * j] % mod[0][2 * j] == G[i] % mod[0][2 * j]) ans++;
			if(dist[1][2 * j] != -1)
				if(dist[1][2 * j] <= G[i] && dist[1][2 * j] % mod[1][2 * j] == G[i] % mod[1][2 * j]) ans++;
		}
		answer(ans);
	}
}

void bfs(int ini){
	queue<int> fila;
	for(int i = 0; i < n; i++){
		dist[0][2 * i] = -1;
		dist[0][2 * i + 1] = -1;
		dist[1][2 * i] = -1;
		dist[1][2 * i + 1] = -1;
	}
	dist[0][2 * ini] = 0;
	mod[0][2 * ini] = cycleSize[0];
	fila.push(2 * ini);
	while(!fila.empty()){
		int cur = fila.front();
		fila.pop();
		for(int i = 0; i < rev[cur].size(); i++){
			int viz = rev[cur][i];
			if(dist[0][viz] != -1) continue;
			fila.push(viz);
			dist[0][viz] = dist[0][cur] + 1;
			mod[0][viz] = mod[0][cur];
		}
	}
	dist[1][2 * ini + 1] = 0;
	mod[1][2 * ini + 1] = cycleSize[1];
	fila.push(2 * ini + 1);
	while(!fila.empty()){
		int cur = fila.front();
		fila.pop();
		for(int i = 0; i < rev[cur].size(); i++){
			int viz = rev[cur][i];
			if(dist[1][viz] != -1) continue;
			fila.push(viz);
			dist[1][viz] = dist[1][cur] + 1;
			mod[1][viz] = mod[1][cur];
		}
	}
}

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 + 1]){
		int cur = 2 * p + 1;
		while(marc[cur] == 0){
			marc[cur] = 1;
			cycleSize[1]++;
			cur = ar[cur];
		}
	}
	else cycleSize[1] = INF;
	if(!marc[2 * p]){
		int cur = 2 * p;
		while(marc[cur] == 0){
			marc[cur] = 1;
			cycleSize[0]++;
			cur = ar[cur];
		}
	}
	else cycleSize[0] = INF;
}

Compilation message (stderr)

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