Submission #1307544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307544		marcogambaro	Tropical Garden (IOI11_garden)	C++20	Compilation error	0 ms	0 KiB

garden

#include <bits/stdc++.h>
using namespace std;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define readv(v) do { for(auto &i: v) cin >> i; } while(0)
#define writev(v) do { for(auto i: v) cout << i << " "; } while(0)
#define _ << " " <<
#define ll long long
#define u64 unsigned long long
#ifndef MARCO
bool dbg = 0;
#define info(str, ...)
#define infon(str, ...)
#else
bool dbg = 1;
#define info(str, ...) do { fprintf(stderr, "\033[31m" str "\033[0m", ##__VA_ARGS__); } while(0)
#define infon(str, ...) do { fprintf(stderr, "\033[31m" str "\033[0m\n", ##__VA_ARGS__); } while(0)
#endif
constexpr int LOG = 30;

#define int long long

struct cycle{
	ll T, q; //ans = q + k*T

	bool operator==(const cycle &o) const {
		return (T == o.T) & (q == o.q);
	}
};
cycle lost = {-1, -1};

int N, P, Q;
vector<cycle> rgood, rbad; //risposta se arrivo in quel nodo dall'arco più bello o no
vector<int> onegood, onebad;
vector<int> G1, G2;

vector<int> statgood, statbad; //0 = mai visto, >0 = in esecuzione, -1 = finito 

int esplorabad(int a, int b, int c);
int esploragood(int a, int b, int c);

int esplorabad(int n, int k, int seenP) {
	if(n == P)	seenP = 0;
	if(statbad[n] == -1) return 0;
	if(statbad[n] > 0) {
		//il ciclo ha lunghezza k-statbad[n]
		if(seenP < 0)	rbad[n] = lost;
		else 			rbad[n] = {k - statbad[n], k - statbad[n] - seenP};
		statbad[n] = -1;
		return 1;
	}
	
	statbad[n] = k;
	int n2 = G2[n];
	if(n == G1[n2] && G2[n2] != -1) {
		int rtn;
		if(esplorabad(n2, k+1, seenP+1) == 0) { //fuori da un ciclo
			if(rbad[n2] == lost) 	rbad[n] = lost;
			else 					rbad[n] = {rbad[n2].T, rbad[n2].q+1};
			statbad[n] = -1;
			rtn = 0;
		}
		else { //dentro un ciclo
			rtn = 1;
			if(statbad[n] == -1) 		rtn = 0; //fine del ciclo
			else if(rbad[n2] == lost) 	rbad[n] = lost;
			else						rbad[n] = {rbad[n2].T, (rbad[n2].q+1)%rbad[n2].T};
			statbad[n] = -1;
		}

		if(seenP == 0) 	onebad[n] = 0;
		else			onebad[n] = onebad[n2]+1;
		return rtn;
	}
	else {
		int rtn;
		if(esploragood(n2, k+1, seenP+1) == 0) { //fuori da un ciclo
			if(rgood[n2] == lost) 	rbad[n] = lost;
			else 					rbad[n] = {rgood[n2].T, rgood[n2].q+1};
			statbad[n] = -1;
			rtn = 0;
		}
		else { //dentro un ciclo
			rtn = 1;
			if(statbad[n] == -1) 		rtn = 0; //fine del ciclo
			else if(rbad[n2] == lost) 	rbad[n] = lost;
			else						rbad[n] = {rgood[n2].T, (rgood[n2].q+1)%rgood[n2].T};
			statbad[n] = -1;
		}

		if(seenP == 0) 	onebad[n] = 0;
		else			onebad[n] = onegood[n2]+1;
		return rtn;
	}
}

int esploragood(int n, int k, int seenP) {
	if(n == P)	seenP = 0;
	if(statgood[n] == -1) return 0;
	if(statgood[n] > 0) {
		//il ciclo ha lunghezza k-statgood[n]
		if(seenP < 0)	rgood[n] = lost;
		else 			rgood[n] = {k - statgood[n], k - statgood[n] - seenP};
		statgood[n] = -1;
		return 1;
	}
	
	statgood[n] = k;
	int n2 = G1[n];
	if(n == G1[n2] && G2[n2] != -1) {
		int rtn;
		if(esplorabad(n2, k+1, seenP+1) == 0) { //fuori da un ciclo
			if(rbad[n2] == lost) 	rgood[n] = lost;
			else 					rgood[n] = {rbad[n2].T, rbad[n2].q+1};
			statgood[n] = -1;
			rtn = 0;
		}
		else { //dentro un ciclo
			rtn = 1;
			if(statgood[n] == -1) 		rtn = 0; //fine del ciclo
			else if(rbad[n2] == lost) 	rgood[n] = lost;
			else						rgood[n] = {rbad[n2].T, (rbad[n2].q+1)%rbad[n2].T};
			statgood[n] = -1;
		}

		if(seenP == 0) 	onegood[n] = 0;
		else 			onegood[n] = onebad[n2]+1;
		return rtn;
	}
	else {
		int rtn;
		if(esploragood(n2, k+1, seenP+1) == 0) { //fuori da un ciclo
			if(rgood[n2] == lost) 	rgood[n] = lost;
			else 					rgood[n] = {rgood[n2].T, rgood[n2].q+1};
			statgood[n] = -1;
			rtn = 0;
		}
		else { //dentro un ciclo
			rtn = 1;
			if(statgood[n] == -1) 		rtn = 0; //fine del ciclo
			else if(rbad[n2] == lost) 	rgood[n] = lost;
			else						rgood[n] = {rgood[n2].T, (rgood[n2].q+1)%rgood[n2].T};
			statgood[n] = -1;
		}

		if(seenP == 0) 	onegood[n] = 0;
		else 			onegood[n] = onegood[n2]+1;
		return rtn;
	}
}


signed main(){	
	#ifndef MARCO
	ios::sync_with_stdio(false);
	cin.tie(nullptr); 
	ifstream cin("input.txt");
	ofstream cout("output.txt");
	#endif  
    
	int M; 
    cin >> N >> M >> P;
    G1.resize(N, -1);
	G2.resize(N, -1);

	for(int i=0; i<M; i++) {
		int a, b; cin >> a >> b;
		if(G1[a] == -1) 		G1[a] = b;
		else if(G2[a] == -1) 	G2[a] = b;
		swap(a, b);
		if(G1[a] == -1) 		G1[a] = b;
		else if(G2[a] == -1) 	G2[a] = b;
	}
    
	rgood.resize(N);
	rbad.resize(N);
	statgood.resize(N);
	statbad.resize(N);
	onegood.resize(N, -1e9);
	onebad.resize(N, -1e9);

	for(int i=N-1; i>=0; i--) {
		esploragood(i, 1, -1e9);
	}

	if(dbg) {
		infon("\ndebugging...");
		infon("rgood:");
		info("T: "); for(int i=0; i<N; i++) cout << rgood[i].T << " "; cout << "\n";
		info("q: "); for(int i=0; i<N; i++) cout << rgood[i].q << " "; cout << "\n";
		infon("rbad:");
		info("T: "); for(int i=0; i<N; i++) cout << rbad[i].T << " "; cout << "\n";
		info("q: "); for(int i=0; i<N; i++) cout << rbad[i].q << " "; cout << "\n";
		infon("onegood: ");
		for(int i: onegood) cout << i << " "; cout << "\n";
		infon("onebad: ");
		for(int i: onebad) cout << i << " "; cout << "\n";
	}

	int Q; cin >> Q;
	while(Q--) {
		ll x; cin >> x;
		int ans = 0;

		int i=-1;
		for(auto &[T, q]: rgood) {
			i++;
			if(onegood[i] == x) {
				ans++;
				continue;
			}
			if(T <= 0) continue;

			if(x-q >= 0 && (x-q)%T == 0) ans++;
		}

		cout << ans << "\n";
	}


}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccZvO3F3.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccxnMbFZ.o:garden.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccZvO3F3.o: in function `main':
grader.cpp:(.text.startup+0x3f): undefined reference to `count_routes(int, int, int, int (*) [2], int, int*)'
collect2: error: ld returned 1 exit status