제출 #261652

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
261652		super_j6	열대 식물원 (Tropical Garden) (IOI11_garden)	C++14	100 / 100	4644 ms	30460 KiB

garden

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second
 
const int inf = 0x3f3f3f3f;
const int mxn = 300000;
int a[mxn][2], f[mxn][2];
int d[mxn], p[mxn], vis[mxn];
vector<int> g[mxn];
int ans[mxn];
 
void dfs(int c){
	vis[c] = 1;
	for(int i : g[c]){
		if(vis[i]) continue;
		d[i] = d[c] + 1;
		dfs(i);
	}
}

void answer(int x);
 
void count_routes(int n, int m, int k, int e[][2], int q, int qr[]){
	memset(a, inf, sizeof(a));
	memset(p, -1, sizeof(p));
	for(int i = 0; i < m; i++)
	for(int j = 0; j < 2; j++){
		int x = e[i][j];
		a[x][1] = min(a[x][1], i);
		sort(a[x], a[x] + 2);
	}
	
	for(int i = 0; i < n; i++){
		if(a[i][0] == inf){
			p[i] = i;
			g[i].push_back(i);
		}
	} 
	for(int i = 0; i < m; i++)
	for(int j = 0; j < 2; j++){
		int x = e[i][j], y = e[i][!j];
		for(int l = 0; l < 2; l++){
			if(a[x][l] == i){
				int u = (a[y][0] == i && a[y][1] != inf) * n + y, v = l * n + x;
				p[v] = u;
				g[u].push_back(v);
			} 
		}
	}
	
	for(int t = 0; t < 2; t++){
		memset(d, inf, sizeof(d));
		memset(vis, 0, sizeof(vis));
		
		int x = t * n + k, y, l;
		for(y = x; ~y && !vis[y]; y = p[y]) vis[y] = 1;
		for(int i = p[x]; i != y; i = p[i]) vis[i] = 0;
		
		d[x] = 0;
		dfs(x);
		if(x == y) l = d[p[x]] + 1;
		for(int i = 0; i < n; i++)
		for(int j = 0; j < q; j++){
			if(x != y) ans[j] += d[i] == qr[j];
			else ans[j] += d[i] <= qr[j] && (d[i] % l) == (qr[j] % l);
		}
	}
	
	for(int i = 0; i < q; i++) answer(ans[i]);
}

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

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:73:57: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
    else ans[j] += d[i] <= qr[j] && (d[i] % l) == (qr[j] % l);
                                                  ~~~~~~~^~~~

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