제출 #294263

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
294263		crackersamdjam	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	컴파일 에러	0 ms	0 KiB

garden

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define gc getchar()
#define pc(x) putchar(x)
template<typename T> void scan(T &x){x = 0;bool _=0;T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=char(n%10+48);n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}
#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
template<typename T>
void pr(T a){std::cerr<<a<<std::endl;}
template<typename T,typename... Args>
void pr(T a, Args... args) {std::cerr<<a<<' ',pr(args...);}
#else
template<typename... Args>
void pr(Args... args){}
#endif

#define f first
#define s second

using namespace std;
using pii = pair<int, int>;
const int MM = 150005;

int n, m, p, k;
vector<pii> in[MM];
pii nx[MM][2];
int dis[MM][2], f[MM], s[MM], len, id, cnt[MM], cnta[MM], cntb[MM];
bool vis[MM][2];
//0 = go to best next one
//1 = go to second best one

#ifndef ONLINE_JUDGE
void answer(int X){
	print(X);
}
#endif

void go(int cur, bool f, int d){
	pr("go", cur, f, d);
	vis[cur][f] = 1;
	int u, w;
	tie(u, w) = nx[cur][f];
	if(u == p){
		len = d+1;
		id = f;
		return;
	}
	if(!vis[u][w])
		go(u, w, d+1);
}

int dfs(int cur, bool f){
	if(~dis[cur][f])
		return dis[cur][f];
	dis[cur][f] = 1e9;
	return dis[cur][f] = dfs(nx[cur][f].first, nx[cur][f].second)+1;
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
	n = N, m = M, p = P, k = Q;
	for(int i = 0; i < m; i++){
		in[R[i][0]].emplace_back(i, R[i][1]);
		in[R[i][1]].emplace_back(i, R[i][0]);
	}
	for(int i = 0; i < n; i++){
		sort(all(in[i]));
		assert(size(in[i]));
		if(size(in[i]) == 1)
			in[i].emplace_back(in[i][0]);
		else
			in[i].resize(2);
	}
	for(int i = 0,u,w; i < n; i++){
		tie(w, u) = in[i][0];
		nx[i][0] = {u, (w == in[u][0].first)};
		tie(w, u) = in[i][1];
		nx[i][1] = {u, (w == in[u][0].first)};
		pr("nx", i, nx[i][0].f, nx[i][0].s, nx[i][1].f, nx[i][1].s);
	}
	//find "final" cycle distances
	memset(vis, 0, sizeof vis);
	len = 1e9, id = -1;
	go(p, 0, 0);
	int lena = len, ida = id;
	pr("a", lena, ida);

	memset(vis, 0, sizeof vis);
	len = 1e9, id = -1;
	go(p, 1, 0);
	int lenb = len, idb = id;
	pr("b", lenb, idb);

	// either no cycle, 0/1 itself cycle, lead into other cycle, or large cycle with both...

	int moda, offa, modb, offb;
	if(ida == -1){
		moda = 1e9;
		offa = 1e9;
	}
	else if(ida == 0){
		moda = lena;
		offa = 0;
	}
	else{
		moda = lenb;
		offa = lena;
	}

	if(idb == -1){
		modb = 1e9;
		offb = 1e9;
	}
	else if(idb == 1){
		modb = lenb;
		offb = 0;
	}
	else{
		modb = lena;
		offb = lenb;
	}

	if(ida == 1 and idb == 0){
		//large cycle with both
		// abort();
	}

	pr("vals", moda, offa, modb, offb, ida, idb);

	memset(dis, -1, sizeof dis);
	dis[p][0] =  0;
	dis[p][1] = 1e8; //to tell apart
	// for(int i = 0; i < n; i++){
	// 	int l = dfs(i, 0);
	// 	pr("l", i, l);
	// 	if(l >= 1e9) continue;
	// 	if(l >= 1e8){
	// 		//2nd cycle
	// 		l -= 1e8;
	// 		if(modb != 1e9)
	// 			cntb[(l+offb)%modb]++;
	// 		if((l+offb)%modb != l)
	// 			cnt[l]++;
	// 	}
	// 	else{
	// 		//1st cycle
	// 		if(moda != 1e9)
	// 			cnta[(l+offa)%moda]++;
	// 		if((l+offa)%moda != l)
	// 			cnt[l]++;
	// 	}
	// }
	int mod2 = (moda+modb);
	for(int i = 0; i < Q; i++){
		int v = G[i], ans = 0;
		for(int j = 0; j < n; j++){
			int l = dfs(j, 0);
			pr("d", j, l);
			if(l >= 1e9) continue;

			//large cycle with both
			if(ida == 1 and idb == 0){
				if(l >= 1e8){
					l -= 1e8;
					if(l <= v){
						l %= mod2;
						v %= mod2;
						if(l == v or (l+offb)%mod2 == v)
							ans++;
					}
				}
				else{
					if(l <= v){
						l %= mod2;
						v %= mod2;
						if(l == v or (l+offa)%mod2 == v)
							ans++;
					}
				}
				continue;
			}
			
			if(l >= 1e8){
				l -= 1e8;
				//second cycle
				if(l == v or (l+offb <= v and (l+offb)%modb == v%modb))
					ans++;
			}
			else{
				if(l == v or (l+offa <= v and (l+offa)%moda == v%moda))
					ans++;
			}
		}
		// if(moda != 1e9)
		// 	ans += cnta[v%moda];
		// if(modb != 1e9)
		// 	ans += cntb[v%modb];
		// ans += cnt[v];
		answer(ans);
	}
}

#ifndef ONLINE_JUDGE
int main(){
	int N, M, P;
	scan(N, M, P);
	int R[M][2];
	for(int i = 0; i < M; i++){
		scan(R[i][0], R[i][1]);
		// print(R[i][0], R[i][1], i);
	}
	int Q;
	scan(Q);
	int G[Q];
	for(int i = 0; i < Q; i++)
		scan(G[i]);
	count_routes(N, M, P, R, Q, G);

	if(0){
		int G[] = {3};
		int R[][2] = {{1, 2}, {0, 1}, {0, 3}, {3, 4}, {4, 5}, {1, 5}};
		count_routes(6, 6, 0, R, 1, G);
	}
	if(0){
		int G[] = {3, 1};
		int R[][2] = {{1, 0}, {1, 2}, {3, 2}, {1, 3}, {4, 2}};
		count_routes(5, 5, 2, R, 2, G);
	}
}
#endif

컴파일 시 표준 에러 (stderr) 메시지

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:202:3: error: 'answer' was not declared in this scope
  202 |   answer(ans);
      |   ^~~~~~