oj.uz

Submission #559753

# Submission time Handle Problem Language Result Execution time Memory
559753 2022-05-10T13:50:30 Z keta_tsimakuridze Tropical Garden (IOI11_garden) C++14
49 / 100
 158 ms 36100 KB 
#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;
	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);
	}
}

Compilation message

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

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19156 KB Output is correct
2 Correct 11 ms 19204 KB Output is correct
3 Correct 11 ms 19180 KB Output is correct
4 Correct 11 ms 19132 KB Output is correct
5 Correct 10 ms 19156 KB Output is correct
6 Correct 13 ms 19284 KB Output is correct
7 Correct 12 ms 19044 KB Output is correct
8 Correct 10 ms 19132 KB Output is correct
9 Correct 11 ms 19204 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19156 KB Output is correct
2 Correct 11 ms 19204 KB Output is correct
3 Correct 11 ms 19180 KB Output is correct
4 Correct 11 ms 19132 KB Output is correct
5 Correct 10 ms 19156 KB Output is correct
6 Correct 13 ms 19284 KB Output is correct
7 Correct 12 ms 19044 KB Output is correct
8 Correct 10 ms 19132 KB Output is correct
9 Correct 11 ms 19204 KB Output is correct
10 Correct 9 ms 19044 KB Output is correct
11 Correct 18 ms 21816 KB Output is correct
12 Correct 33 ms 23484 KB Output is correct
13 Correct 51 ms 31180 KB Output is correct
14 Correct 103 ms 34176 KB Output is correct
15 Correct 158 ms 36100 KB Output is correct
16 Correct 129 ms 31460 KB Output is correct
17 Incorrect 96 ms 29992 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19156 KB Output is correct
2 Correct 11 ms 19204 KB Output is correct
3 Correct 11 ms 19180 KB Output is correct
4 Correct 11 ms 19132 KB Output is correct
5 Correct 10 ms 19156 KB Output is correct
6 Correct 13 ms 19284 KB Output is correct
7 Correct 12 ms 19044 KB Output is correct
8 Correct 10 ms 19132 KB Output is correct
9 Correct 11 ms 19204 KB Output is correct
10 Correct 9 ms 19044 KB Output is correct
11 Correct 18 ms 21816 KB Output is correct
12 Correct 33 ms 23484 KB Output is correct
13 Correct 51 ms 31180 KB Output is correct
14 Correct 103 ms 34176 KB Output is correct
15 Correct 158 ms 36100 KB Output is correct
16 Correct 129 ms 31460 KB Output is correct
17 Incorrect 96 ms 29992 KB Output isn't correct
18 Halted 0 ms 0 KB -