oj.uz

Submission #260015

# Submission time Handle Problem Language Result Execution time Memory
260015 2020-08-08T23:40:33 Z amiratou Tropical Garden (IOI11_garden) C++14
69 / 100
 5000 ms 65912 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define sz(x) (int)(x.size())
#define pb push_back
const int MX = 450005,L=30;

vector<pair<int,int> > vec[150005];
int up[MX][L],curr[150005];

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
	for (int i = 0; i < M; ++i)
	{
		vec[R[i][0]].pb({R[i][1],i});
		vec[R[i][1]].pb({R[i][0],M+i});
	}
	for (int i = 0; i < N; ++i)
	{
		multiset<pair<int,int> > myset;
		for (int j = 0; j < sz(vec[i]); ++j)
		{
			int val=vec[i][j].se-((vec[i][j].se>=M)?M:0);
			myset.insert({val,j});
		}
		for (int j = 0; j < sz(vec[i]); ++j)
		{
			int val=vec[i][j].se-((vec[i][j].se>=M)?M:0);
			int c=val+((vec[i][j].se>=M)?0:M);
			myset.erase(myset.find({val,j}));
			if(!sz(myset))up[c][0]=vec[i][j].se;
			else up[c][0]=vec[i][myset.begin()->se].se;
			myset.insert({val,j});
		}
		up[i+2*M][0]=vec[i][myset.begin()->se].se;
	}
	for (int i = 1; i < L; ++i)
		for (int j = 0; j < 2*M+N; ++j)
			up[j][i]=up[up[j][i-1]][i-1];
	for (int i = 0; i < Q; ++i)
	{
		int ans=0;
		for (int j = 0; j < N; ++j)
			curr[j]=2*M+j;
		for (int j = 0; j < L; ++j)
		{
			if(!((G[i]>>j)&1))continue;
			for (int z = 0; z < N; ++z)
				curr[z]=up[curr[z]][j];
		}
		for (int j = 0; j < N; ++j)
			ans+=(((curr[j]>=M)?R[curr[j]-M][0]:R[curr[j]][1])==P);
		answer(ans);
	}
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4224 KB Output is correct
2 Correct 4 ms 4224 KB Output is correct
3 Correct 4 ms 4352 KB Output is correct
4 Correct 4 ms 3840 KB Output is correct
5 Correct 3 ms 3840 KB Output is correct
6 Correct 5 ms 4608 KB Output is correct
7 Correct 3 ms 3968 KB Output is correct
8 Correct 4 ms 4224 KB Output is correct
9 Correct 11 ms 6272 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4224 KB Output is correct
2 Correct 4 ms 4224 KB Output is correct
3 Correct 4 ms 4352 KB Output is correct
4 Correct 4 ms 3840 KB Output is correct
5 Correct 3 ms 3840 KB Output is correct
6 Correct 5 ms 4608 KB Output is correct
7 Correct 3 ms 3968 KB Output is correct
8 Correct 4 ms 4224 KB Output is correct
9 Correct 11 ms 6272 KB Output is correct
10 Correct 3 ms 3968 KB Output is correct
11 Correct 35 ms 13056 KB Output is correct
12 Correct 101 ms 23672 KB Output is correct
13 Correct 178 ms 38648 KB Output is correct
14 Correct 299 ms 61820 KB Output is correct
15 Correct 310 ms 63820 KB Output is correct
16 Correct 270 ms 54392 KB Output is correct
17 Correct 263 ms 52468 KB Output is correct
18 Correct 101 ms 23672 KB Output is correct
19 Correct 294 ms 61816 KB Output is correct
20 Correct 314 ms 63864 KB Output is correct
21 Correct 272 ms 54264 KB Output is correct
22 Correct 265 ms 52216 KB Output is correct
23 Correct 326 ms 65912 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4224 KB Output is correct
2 Correct 4 ms 4224 KB Output is correct
3 Correct 4 ms 4352 KB Output is correct
4 Correct 4 ms 3840 KB Output is correct
5 Correct 3 ms 3840 KB Output is correct
6 Correct 5 ms 4608 KB Output is correct
7 Correct 3 ms 3968 KB Output is correct
8 Correct 4 ms 4224 KB Output is correct
9 Correct 11 ms 6272 KB Output is correct
10 Correct 3 ms 3968 KB Output is correct
11 Correct 35 ms 13056 KB Output is correct
12 Correct 101 ms 23672 KB Output is correct
13 Correct 178 ms 38648 KB Output is correct
14 Correct 299 ms 61820 KB Output is correct
15 Correct 310 ms 63820 KB Output is correct
16 Correct 270 ms 54392 KB Output is correct
17 Correct 263 ms 52468 KB Output is correct
18 Correct 101 ms 23672 KB Output is correct
19 Correct 294 ms 61816 KB Output is correct
20 Correct 314 ms 63864 KB Output is correct
21 Correct 272 ms 54264 KB Output is correct
22 Correct 265 ms 52216 KB Output is correct
23 Correct 326 ms 65912 KB Output is correct
24 Correct 6 ms 3968 KB Output is correct
25 Correct 1360 ms 13176 KB Output is correct
26 Correct 2618 ms 23672 KB Output is correct
27 Execution timed out 5040 ms 38648 KB Time limit exceeded
28 Halted 0 ms 0 KB -