제출 #559752

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

garden

#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>
using namespace std;
//#include "garden.h"
//#include "gardenlib.h"
/*
#include <stdio.h>
#include <stdlib.h>

#define MAX_M  1000000
#define MAX_Q  2000

static int N, M, P, Q;
static int R[MAX_M][2];
static int G[MAX_Q];
static int solutions[MAX_Q];
static int answers[MAX_Q];
static int answer_count;

inline 
void my_assert(int e) {if (!e) abort();}
void read_input()
{
  int i;
  my_assert(3==scanf("%d %d %d",&N,&M,&P));
  for(i=0; i<M; i++)
    my_assert(2==scanf("%d %d",&R[i][0],&R[i][1]));
  my_assert(1==scanf("%d",&Q));
  for(i=0; i<Q; i++)
    my_assert(1==scanf("%d",&G[i]));
  for(i=0; i<Q; i++)
    my_assert(1==scanf("%d",&solutions[i]));
}

void answer(int x)
{ cout << "+" << x << endl;
  if(answer_count>=Q) {
    printf("Incorrect.  Too many answers.\n");
    exit(0);
  }
  answers[answer_count] = x;
}
*/
const int Nn = 2e5 + 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;
	while(f[u] != 2) {
		par[u][t] = 1;
		f[u] = 2;
		u = to[u];
	}
	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;
	vector<int> cyc(2);
	cyc[0] = calc(0, id[p][0]); cyc[1] = calc(1, id[p][1]); 
	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)) ++cnt;
			else if((!in_cycle[id[p][1]] && G[i] == d[id[j][0]][1]) 
			|| (in_cycle[id[p][0]] && G[i] >= d[id[j][0]][1] && (G[i] - d[id[j][0]][1]) % cyc[1] == 0)) ++cnt;
		}
		answer(cnt);
	}
}

/*
int main()
{
  int correct, i;

  read_input();
  answer_count = 0;
  count_routes(N,M,P,R,Q,G);

  if(answer_count!=Q) {
    printf("Incorrect.  Too few answers.\n");
    exit(0);
  }

  correct = 1;
  for(i=0; i<Q; i++)
    if(answers[i]!=solutions[i])
      correct = 0;
  if(correct)
    printf("Correct.\n");
  else {
    printf("Incorrect.\n");
    printf("Expected: ");
    for(i=0; i<Q; i++)
      printf("%d ",solutions[i]);
    printf("\nReturned: ");
    for(i=0; i<Q; i++)
      printf("%d ",answers[i]);
  }
  return 0;
}  */

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

garden.cpp: In function 'int calc(int, int)':
garden.cpp:76:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   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:100:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |   for(int j = 0; j < V[i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~

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