제출 #559758

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

garden

#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
const int Nn = 4e5 + 5;
int f[Nn], par[Nn][2], d[Nn][2], id[Nn][2], cur, to[Nn], in_cycle[Nn];
vector<int> V[Nn], from[Nn];
int calc(int t, int u) {
	int U = u;
	for(int i = 1; i <= cur; i++) f[i] = 0;
	
	while(!f[u]) {
		f[u] = 1;
		u = to[u];
	}
	int sz = 0;
	while(f[u] != 2) {
		f[u] = 2;
		u = to[u];
		++sz;
	}
	u = U;
	if(f[u] == 2) in_cycle[u] = 1;
	d[u][t] = 0; 
	queue<int> q; q.push(u);
	while(q.size()) {
		int u = q.front();
		q.pop();
		for(int i = 0; i < from[u].size(); i++) { 
			if(d[from[u][i]][t] <= d[u][t] + 1) continue;
			d[from[u][i]][t] = d[u][t] + 1;
			q.push(from[u][i]);
		}
	}
	return sz;
}
void count_routes(int N, int M, int p, int R[][2], int Q, int G[])
{
	++p;
	for(int i = 1; i <= N; i++) {
		
		id[i][0] = ++ cur;
		id[i][1] = ++ cur;
	}
	for(int i = 0; i < M; i++) {
		int u = R[i][0], v = R[i][1];
		++u, ++v;
		if(V[u].size() < 2) V[u].push_back(v);
		if(V[v].size() < 2) V[v].push_back(u);
	}
	
	for(int i = 1; i <= N; i++) {
		for(int j = 0; j < V[i].size(); j++) {
			to[id[i][j]] = id[V[i][j]][0];
			if(V[V[i][j]][0] == i && V[V[i][j]].size() > 1) {
				to[id[i][j]] = id[V[i][j]][1];
			}
			from[to[id[i][j]]].push_back(id[i][j]);
		}
	}
	for(int i = 1; i <= cur; i++) for(int t = 0; t < 2; t++) d[i][t] = 1e9 + 16;
	vector<int> cyc(2);
	cyc[0] = calc(0, id[p][0]); cyc[1] = calc(1, id[p][1]); 
	int x = 1e9;
	for(int i = 0; i < Q; i++) {
		int cnt = 0;
		for(int j = 1; j <= N; j++) {
			if(((!in_cycle[id[p][0]] && G[i] == d[id[j][0]][0]) 
			|| (in_cycle[id[p][0]] && G[i] >= d[id[j][0]][0] && (G[i] - d[id[j][0]][0]) % cyc[0] == 0)) && d[id[j][0]][0] <= x) ++cnt;
			else if(((!in_cycle[id[p][1]] && G[i] == d[id[j][0]][1]) 
			|| (in_cycle[id[p][1]] && G[i] >= d[id[j][0]][1] && (G[i] - d[id[j][0]][1]) % cyc[1] == 0)) && d[id[j][0]][1] <= x) ++cnt;
		}
		answer(cnt);
	}
}

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

garden.cpp: In function 'int calc(int, int)':
garden.cpp:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for(int i = 0; i < from[u].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:53:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for(int j = 0; j < V[i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~

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