oj.uz

Submission #100652

# Submission time Handle Problem Language Result Execution time Memory
100652 2019-03-13T05:20:49 Z Pro_ktmr None (JOI16_snowy) C++14
55 / 100
 26 ms 1460 KB 
#include"bits/stdc++.h"
using namespace std;
#include"Anyalib.h"
#define MP(a,b) make_pair(a,b)

static int n;
static int par[500];
static int toPar[500];

static int d[500] = {};
static int depth(int i){
	if(i == 0) return 0;
	if(d[i] != 0) return d[i];
	return d[i] = 1 + depth(par[i]);
}
static vector<int> ls;

void InitAnya(int N, int A[], int B[]){
	n = N;
	vector<pair<int,int> > tonari[500];
	for(int i=0; i<N-1; i++){
		tonari[A[i]].push_back(MP(B[i],i));
		tonari[B[i]].push_back(MP(A[i],i));
	}
	
	par[0] = 0;
	toPar[0] = -1;
	queue<int> que;
	que.push(0);
	while(!que.empty()){
		int now = que.front();
		que.pop();
		for(int i=0; i<tonari[now].size(); i++){
			if(tonari[now][i].first == par[now]) continue;
			par[tonari[now][i].first] = now;
			toPar[tonari[now][i].first] = tonari[now][i].second;
			que.push(tonari[now][i].first);
		}
	}
	
	for(int i=0; i<n; i++){
		if(depth(i)%10 == 0) ls.push_back(i);
	}
	ls.push_back(n);
}

//void Save(int place, int bit)

static int C2[500];
static int memo[500];
static int wa(int i){
	if(memo[i] != -1) return memo[i];
	return memo[i] = wa(par[i]) + C2[toPar[i]];
}
void Anya(int C[]){
	for(int i=1; i<n; i++) Save(i, C[toPar[i]]);
	
	for(int i=0; i<n-1; i++) C2[i] = C[i];
	for(int i=0; i<n; i++) memo[i] = -1;
	memo[0] = 0;
	for(int i=0; i<n; i++){
		int tmp = wa(i);
		if(*lower_bound(ls.begin(), ls.end(), i) == i){
			int idx = lower_bound(ls.begin(), ls.end(), i) - ls.begin();
			for(int j=0; j<10; j++){
				Save(500+idx*10+j, (tmp>>(9-j))%2);
			}
		}
	}
}

#include"bits/stdc++.h"
using namespace std;
#include"Borislib.h"
#define MP(a,b) make_pair(a,b)

static int n;
static int par[500];
static int toPar[500];


static int d[500] = {};
static int depth(int i){
	if(i == 0) return 0;
	if(d[i] != 0) return d[i];
	return d[i] = 1 + depth(par[i]);
}
static vector<int> ls;

void InitBoris(int N, int A[], int B[]){
	n = N;
	vector<pair<int,int> > tonari[500];
	for(int i=0; i<N-1; i++){
		tonari[A[i]].push_back(MP(B[i],i));
		tonari[B[i]].push_back(MP(A[i],i));
	}
	par[0] = 0;
	queue<int> que;
	que.push(0);
	while(!que.empty()){
		int now = que.front();
		que.pop();
		for(int i=0; i<tonari[now].size(); i++){
			if(tonari[now][i].first == par[now]) continue;
			par[tonari[now][i].first] = now;
			toPar[tonari[now][i].first] = tonari[now][i].second;
			que.push(tonari[now][i].first);
		}
	}
	
	for(int i=0; i<n; i++){
		if(depth(i)%10 == 0) ls.push_back(i);
	}
}

//Ask(int place)
int Boris(int city){
	int ans = 0;
	int now = city;
	while(*lower_bound(ls.begin(), ls.end(), now) != now){
		ans += Ask(now);
		now = par[now];
	}
	int idx = lower_bound(ls.begin(), ls.end(), now) - ls.begin();
	for(int i=0; i<10; i++){
		ans += Ask(500+idx*10+i)<<(9-i);
	}
	return ans;
}

Compilation message

Anya.cpp: In function 'void InitAnya(int, int*, int*)':
Anya.cpp:33:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<tonari[now].size(); i++){
                ~^~~~~~~~~~~~~~~~~~~

Boris.cpp: In function 'void InitBoris(int, int*, int*)':
Boris.cpp:32:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<tonari[now].size(); i++){
                ~^~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 904 KB Output is correct
2 Correct 4 ms 700 KB Output is correct
3 Correct 8 ms 1068 KB Output is correct
4 Correct 8 ms 1024 KB Output is correct
5 Correct 9 ms 1040 KB Output is correct
6 Correct 10 ms 1304 KB Output is correct
7 Correct 11 ms 1304 KB Output is correct
8 Correct 10 ms 1304 KB Output is correct
9 Correct 11 ms 1280 KB Output is correct
10 Correct 11 ms 1040 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1296 KB Output is correct
2 Correct 13 ms 1044 KB Output is correct
3 Correct 10 ms 1172 KB Output is correct
4 Correct 13 ms 1044 KB Output is correct
5 Correct 14 ms 1408 KB Output is correct
6 Correct 15 ms 1280 KB Output is correct
7 Correct 11 ms 1280 KB Output is correct
8 Correct 11 ms 1172 KB Output is correct
9 Correct 15 ms 1288 KB Output is correct
10 Correct 13 ms 1172 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1280 KB Output is correct
2 Correct 20 ms 1280 KB Output is correct
3 Correct 26 ms 1324 KB Output is correct
4 Correct 20 ms 1280 KB Output is correct
5 Correct 22 ms 1200 KB Output is correct
6 Correct 22 ms 1360 KB Output is correct
7 Correct 23 ms 1460 KB Output is correct
8 Correct 26 ms 1296 KB Output is correct
9 Correct 23 ms 1324 KB Output is correct
10 Correct 24 ms 1324 KB Output is correct
11 Correct 23 ms 1396 KB Output is correct
12 Correct 22 ms 1280 KB Output is correct
13 Correct 20 ms 1280 KB Output is correct
14 Correct 25 ms 1264 KB Output is correct
15 Correct 20 ms 1332 KB Output is correct
16 Correct 20 ms 1324 KB Output is correct
17 Correct 20 ms 1324 KB Output is correct
18 Correct 22 ms 1264 KB Output is correct
19 Correct 19 ms 1324 KB Output is correct
20 Correct 20 ms 1324 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 904 KB Wrong Answer [1]
2 Halted 0 ms 0 KB -