oj.uz

답안 #559752

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
559752 2022-05-10T13:49:56 Z keta_tsimakuridze 열대 식물원 (Tropical Garden) (IOI11_garden) C++14
49 / 100
 70 ms 38236 KB 
#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;
}  */

Compilation message

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.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9812 KB Output is correct
2 Correct 6 ms 9840 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Correct 5 ms 9700 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 6 ms 9912 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 6 ms 9844 KB Output is correct
9 Correct 8 ms 9940 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9812 KB Output is correct
2 Correct 6 ms 9840 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Correct 5 ms 9700 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 6 ms 9912 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 6 ms 9844 KB Output is correct
9 Correct 8 ms 9940 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct
11 Correct 15 ms 12588 KB Output is correct
12 Correct 27 ms 14668 KB Output is correct
13 Correct 44 ms 22612 KB Output is correct
14 Runtime error 70 ms 38236 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9812 KB Output is correct
2 Correct 6 ms 9840 KB Output is correct
3 Correct 6 ms 9812 KB Output is correct
4 Correct 5 ms 9700 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 6 ms 9912 KB Output is correct
7 Correct 6 ms 9684 KB Output is correct
8 Correct 6 ms 9844 KB Output is correct
9 Correct 8 ms 9940 KB Output is correct
10 Correct 6 ms 9684 KB Output is correct
11 Correct 15 ms 12588 KB Output is correct
12 Correct 27 ms 14668 KB Output is correct
13 Correct 44 ms 22612 KB Output is correct
14 Runtime error 70 ms 38236 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -