제출 #899053

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
899053		josanneo22	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	49 / 100	4 ms	2904 KiB

garden

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

#define L(i,j,k) for(int i=j;i<=k;i++)
#define R(i,j,k) for(int i=j;i>=k;i--)

void answer(int x);
constexpr int NN = 1005;
vector<pair<int, int>> GG[NN];
int who1[NN], who2[NN], pos[NN][105], mn1[NN], mn2[NN];
void dfs(int u, int f, int trails) {
	if (u == -1) return;
	if (trails >= 101) return;
	pos[u][trails]++;
	if (who1[u] == -1) dfs(f, u, trails + 1);
	if (f != who1[u]) dfs(who1[u], u, trails + 1);
	else if (f != who2[u] && who2[u] != -1) dfs(who2[u], u, trails + 1);
	else dfs(f, u, trails + 1);
}
void count_routes(int _N, int _M, int _P, int _R[][2], int _Q, int _G[]) {
	int N = _N, M = _M, P = _P, Q = _Q;
	//find the number of nodes that end at P
	L(i, 0, N - 1) {
		who1[i] = who2[i] = -1;
		mn1[i] = mn2[i] = 1E9;
		memset(pos[i], 0, sizeof(pos[i]));
	}
	L(i, 0, M - 1) {
		int u = _R[i][0], v = _R[i][1];
		GG[u].push_back(make_pair(v, i));
		GG[v].push_back(make_pair(u, i));
	}
	L(u, 0, N - 1) {
		for (auto& v : GG[u]) {
			if (v.second < mn1[u]) {
				mn2[u] = mn1[u];
				mn1[u] = v.second;
				who2[u] = who1[u];
				who1[u] = v.first;
			}
			else if (v.second < mn2[u]) {
				mn2[u] = v.second;
				who2[u] = v.first;
			}
		}
	}
	L(i, 0, N - 1) dfs(i, -1, 0);
	L(i, 0, Q - 1) {
		int u = _G[i];
		answer(pos[P][u]);
	}
}

//#include <stdio.h>
//#include <stdlib.h>
//
//#define MAX_M  1000000
//#define MAX_Q  2000
//
//static int N, M, P, Q;
//static int R[MAX_M][2];
//static int G[MAX_Q];
//static int solutions[MAX_Q];
//static int answers[MAX_Q];
//static int answer_count;
//
//inline
//void my_assert(int e) { if (!e) abort(); }
//void read_input()
//{
//	int i;
//	my_assert(3 == scanf("%d %d %d", &N, &M, &P));
//	for (i = 0; i < M; i++)
//		my_assert(2 == scanf("%d %d", &R[i][0], &R[i][1]));
//	my_assert(1 == scanf("%d", &Q));
//	for (i = 0; i < Q; i++)
//		my_assert(1 == scanf("%d", &G[i]));
//	for (i = 0; i < Q; i++)
//		my_assert(1 == scanf("%d", &solutions[i]));
//}
//
//void answer(int x)
//{
//	if (answer_count >= Q) {
//		printf("Incorrect.  Too many answers.\n");
//		exit(0);
//	}
//	answers[answer_count] = x;
//	answer_count++;
//}
//
//int main()
//{
//	int correct, i;
//
//	read_input();
//	answer_count = 0;
//	count_routes(N, M, P, R, Q, G);
//
//	if (answer_count != Q) {
//		printf("Incorrect.  Too few answers.\n");
//		exit(0);
//	}
//
//	correct = 1;
//	for (i = 0; i < Q; i++)
//		if (answers[i] != solutions[i])
//			correct = 0;
//	if (correct)
//		printf("Correct.\n");
//	else {
//		printf("Incorrect.\n");
//		printf("Expected: ");
//		for (i = 0; i < Q; i++)
//			printf("%d ", solutions[i]);
//		printf("\nReturned: ");
//		for (i = 0; i < Q; i++)
//			printf("%d ", answers[i]);
//	}
//	return 0;
//}

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