oj.uz

Submission #559752

# Submission time Handle Problem Language Result Execution time Memory
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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -