Submission #432958

#	Time	Username	Problem	Language	Result	Execution time	Memory
432958		Mounir	열대 식물원 (Tropical Garden) (IOI11_garden)	C++14	0 / 100	6 ms	9932 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
using namespace std;

const int N = 2e5;
int nVus[N], bMax;
int prochain[N * 2];
vector<int> antecedents[N];
int parcours[N];
bool vu[N];
int  tCycle;
map<int, int> nOk;


void dfs(int noeud, int prof){
	if (noeud < bMax)
		nOk[prof]++;	


	//cout << "DFS " << noeud << " " << prof << endl;

	vu[noeud] = true;
	for (int antecedent : antecedents[noeud]){
		if (!vu[antecedent])
			dfs(antecedent, prof + 1);
	}
}

vector<int> tmp[N];

void count_routes(int nNoeuds, int nAretes, int cible, int R[][2], int nReqs, int G[]){
	bMax = nNoeuds;
	for (int iArete = 0; iArete < nAretes; ++iArete){
		tmp[R[iArete][0]].pb(R[iArete][1]);
		tmp[R[iArete][1]].pb(R[iArete][0]);
	}

	for (int noeud = 0; noeud <  nNoeuds; ++noeud){
		prochain[noeud] = tmp[noeud][0];
		if (tmp[noeud].size() == 1){
			prochain[noeud] += nNoeuds;
			prochain[noeud + nNoeuds] = tmp[noeud][0] + (tmp[tmp[noeud][0]][0] == noeud) * nNoeuds;
		}
		else
			prochain[noeud + nNoeuds] = tmp[noeud][1]+ (tmp[tmp[noeud][1]][0] == noeud) * nNoeuds;

	}


//	cout << "p" << prochain[2] << endl;


	//cout << "proc " << prochain[2] << " " << prochain[2 + nNoeuds] << endl;

	for (int noeud = 0; noeud < 2 * nNoeuds; ++noeud)
		antecedents[prochain[noeud]].pb(noeud);

	vector<int> ans(nReqs, 0);

	for (int depart = cible; depart <= cible + nNoeuds; depart += nNoeuds){
		for (int noeud = 0; noeud < 2 * nNoeuds; ++noeud)
			vu[noeud] = false;
		nOk = {};

		int noeud = depart; tCycle = 0;
		while (!vu[noeud]){
			parcours[tCycle++] = noeud;
			vu[noeud] = true;
			noeud = prochain[noeud];
		}

		bool dansCycle = (noeud == depart);
		if (dansCycle){
			for (int delta = 1; delta < tCycle; ++delta)
				dfs(parcours[tCycle - delta], delta);
		}

		dfs(depart, 0);
	//	cout << "taille " << tCycle << endl;

		for (int iReq = 0; iReq < nReqs; ++iReq)
			for (int dist = G[iReq]; dist > 0; dist -= tCycle)
				ans[iReq] += nOk[G[iReq]];

		//for (pii paire : nOk)
		//	cout << "dist " << paire.first << " " << paire.second << endl;
	}

	for (int a : ans)
		answer(a);
}

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