oj.uz

Submission #100647

# Submission time Handle Problem Language Result Execution time Memory
100647 2019-03-13T04:57:21 Z Pro_ktmr None (JOI16_snowy) C++14
55 / 100
 24 ms 1880 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];
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;
	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);
		}
	}
}

//void Save(int place, int bit)
static int memo[100];
static int C2[99];
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=0; i<n-1; i++) C2[i] = C[i];
	if(n <= 100){
		for(int i=0; i<n; i++) memo[i] = -1;
		memo[0] = 0;
		for(int i=0; i<n; i++){
			int tmp = wa(i);
			for(int j=0; j<10; j++){
				Save(i*10+j, (tmp>>9-j)%2);
			}
		}
	}
	if(n > 100){
		int tmp = 0;
		int next = 0;
		for(int i=0; i<n; i++){
			if(i%10 == 0){
				for(int j=0; j<10; j++){
					Save(next, (tmp>>9-j)%2);
					//cout << (tmp>>9-j)%2;
					next++;
				}
			}
			Save(next, C[i]);
			//cout << C[i];
			next++;
			tmp += C[i];
		}
		//cout << endl;
	}
}

#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];
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);
		}
	}
}

//Ask(int place)
int Boris(int city){
	int ans = 0;
	if(n <= 100){
		for(int i=0; i<10; i++){
			ans += Ask(city*10+i)<<(9-i);
		}
	}
	if(n > 100){
		int idx = city/10;
		idx *= 10;
		idx *= 2;
		for(int i=0; i<10; i++){
			//cout << idx+i << endl;
			ans += Ask(idx+i)<<(9-i);
		}
		for(int i=0; i<city%10; i++){
			//cout << idx+10+i << endl;
			ans += Ask(idx+10+i);
		}
	}
	//cout << ans << endl;
	return ans;
}

Compilation message

Anya.cpp: In function 'void InitAnya(int, int*, int*)':
Anya.cpp:22:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<tonari[now].size(); i++){
                ~^~~~~~~~~~~~~~~~~~~
Anya.cpp: In function 'void Anya(int*)':
Anya.cpp:46:25: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
     Save(i*10+j, (tmp>>9-j)%2);
                        ~^~
Anya.cpp:56:24: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
      Save(next, (tmp>>9-j)%2);
                       ~^~

Boris.cpp: In function 'void InitBoris(int, int*, int*)':
Boris.cpp:22: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 784 KB Output is correct
2 Correct 4 ms 852 KB Output is correct
3 Correct 7 ms 824 KB Output is correct
4 Correct 7 ms 1112 KB Output is correct
5 Correct 12 ms 1040 KB Output is correct
6 Correct 9 ms 1296 KB Output is correct
7 Correct 9 ms 1124 KB Output is correct
8 Correct 10 ms 1296 KB Output is correct
9 Correct 12 ms 1044 KB Output is correct
10 Correct 9 ms 1304 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1224 KB Output is correct
2 Correct 12 ms 1316 KB Output is correct
3 Correct 16 ms 1292 KB Output is correct
4 Correct 13 ms 1316 KB Output is correct
5 Correct 12 ms 1056 KB Output is correct
6 Correct 12 ms 1052 KB Output is correct
7 Correct 16 ms 1308 KB Output is correct
8 Correct 13 ms 1180 KB Output is correct
9 Correct 16 ms 1288 KB Output is correct
10 Correct 16 ms 1052 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1280 KB Output is correct
2 Correct 18 ms 1672 KB Output is correct
3 Correct 16 ms 1792 KB Output is correct
4 Correct 16 ms 1816 KB Output is correct
5 Correct 24 ms 1880 KB Output is correct
6 Correct 17 ms 1836 KB Output is correct
7 Correct 16 ms 1844 KB Output is correct
8 Correct 17 ms 1792 KB Output is correct
9 Correct 17 ms 1844 KB Output is correct
10 Correct 17 ms 1764 KB Output is correct
11 Correct 16 ms 1792 KB Output is correct
12 Correct 15 ms 1836 KB Output is correct
13 Correct 20 ms 1736 KB Output is correct
14 Correct 17 ms 1836 KB Output is correct
15 Correct 17 ms 1812 KB Output is correct
16 Correct 18 ms 1792 KB Output is correct
17 Correct 15 ms 1836 KB Output is correct
18 Correct 19 ms 1792 KB Output is correct
19 Correct 17 ms 1736 KB Output is correct
20 Correct 20 ms 1792 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 1336 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -