oj.uz

Submission #100649

# Submission time Handle Problem Language Result Execution time Memory
100649 2019-03-13T05:12:47 Z Pro_ktmr None (JOI16_snowy) C++14
55 / 100
 26 ms 1536 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);
	}
}

//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(depth(i)%10 == 0){
			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(depth(now)%10 != 0){
		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 776 KB Output is correct
2 Correct 5 ms 840 KB Output is correct
3 Correct 7 ms 824 KB Output is correct
4 Correct 7 ms 1108 KB Output is correct
5 Correct 8 ms 1040 KB Output is correct
6 Correct 11 ms 1040 KB Output is correct
7 Correct 9 ms 1304 KB Output is correct
8 Correct 10 ms 1180 KB Output is correct
9 Correct 13 ms 1168 KB Output is correct
10 Correct 11 ms 1216 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1280 KB Output is correct
2 Correct 16 ms 1324 KB Output is correct
3 Correct 23 ms 1324 KB Output is correct
4 Correct 26 ms 1280 KB Output is correct
5 Correct 20 ms 1288 KB Output is correct
6 Correct 22 ms 1324 KB Output is correct
7 Correct 19 ms 1280 KB Output is correct
8 Correct 18 ms 1280 KB Output is correct
9 Correct 21 ms 1280 KB Output is correct
10 Correct 18 ms 1324 KB Output is correct
11 Correct 17 ms 1280 KB Output is correct
12 Correct 19 ms 1280 KB Output is correct
13 Correct 20 ms 1324 KB Output is correct
14 Correct 22 ms 1324 KB Output is correct
15 Correct 23 ms 1324 KB Output is correct
16 Correct 18 ms 1536 KB Output is correct
17 Correct 18 ms 1324 KB Output is correct
18 Correct 18 ms 1424 KB Output is correct
19 Correct 17 ms 1324 KB Output is correct
20 Correct 26 ms 1336 KB Output is correct

Subtask #4
0 / 45.0

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