oj.uz

답안 #100656

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
100656 2019-03-13T05:39:46 Z Pro_ktmr Snowy Roads (JOI16_snowy) C++14
0 / 100
 19 ms 1316 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;


static int c[500] = {};
static int maxDepth = 0;
static bool dp[500][50];
static bool already[500][50] = {};
static bool solve(int last, int nokori){
	if(nokori < 0) return false;
	if(maxDepth <= last+10) return true;
	if(already[last][nokori]) return dp[last][nokori];
	already[last][nokori] = true;
	bool re;
	for(int i=1; i<=10; i++){
		bool tmp = solve(last+i, nokori-c[last+i]);
		re |= tmp;
	}
	return dp[last][nokori] = re;
}
static set<int> v;
static void hukugen(int last, int nokori){
	if(maxDepth <= last+10) return;
	for(int i=1; i<=10; i++){
		if( solve(last+i, nokori-c[last+i]) ){
			v.insert(last+i);
			break;
		}
	}
}

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++){
		c[depth(i)]++;
		maxDepth = max(maxDepth, depth(i));
	}
	solve(0,49);
	v.insert(0);
	hukugen(0,49);
	for(int i=0; i<n; i++){
		if(v.count(depth(i)) == 1) 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(*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;

static int c[500] = {};
static int maxDepth = 0;
static bool dp[500][50];
static bool already[500][50] = {};
static bool solve(int last, int nokori){
	if(nokori < 0) return false;
	if(maxDepth <= last+10) return true;
	if(already[last][nokori]) return dp[last][nokori];
	already[last][nokori] = true;
	bool re;
	for(int i=1; i<=10; i++){
		bool tmp = solve(last+i, nokori-c[last+i]);
		re |= tmp;
	}
	return dp[last][nokori] = re;
}
static set<int> v;
static void hukugen(int last, int nokori){
	if(maxDepth <= last+10) return;
	for(int i=1; i<=10; i++){
		if( solve(last+i, nokori-c[last+i]) ){
			v.insert(last+i);
			break;
		}
	}
}

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++){
		c[depth(i)]++;
		maxDepth = max(maxDepth, depth(i));
	}
	solve(0,49);
	v.insert(0);
	hukugen(0,49);
	for(int i=0; i<n; i++){
		if(v.count(depth(i)) == 1) 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:61:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<tonari[now].size(); i++){
                ~^~~~~~~~~~~~~~~~~~~
Anya.cpp: In function 'bool solve(int, int)':
Anya.cpp:31:6: warning: 're' may be used uninitialized in this function [-Wmaybe-uninitialized]
   re |= tmp;
   ~~~^~~~~~

Boris.cpp: In function 'void InitBoris(int, int*, int*)':
Boris.cpp:58:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<tonari[now].size(); i++){
                ~^~~~~~~~~~~~~~~~~~~
Boris.cpp: In function 'bool solve(int, int)':
Boris.cpp:30:6: warning: 're' may be used uninitialized in this function [-Wmaybe-uninitialized]
   re |= tmp;
   ~~~^~~~~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 784 KB Output is correct
2 Correct 4 ms 788 KB Output is correct
3 Correct 5 ms 1024 KB Output is correct
4 Correct 9 ms 1024 KB Output is correct
5 Correct 9 ms 1280 KB Output is correct
6 Correct 9 ms 1280 KB Output is correct
7 Correct 13 ms 1280 KB Output is correct
8 Correct 12 ms 1168 KB Output is correct
9 Incorrect 7 ms 1280 KB Wrong Answer [6]
10 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 1044 KB Output is correct
2 Incorrect 8 ms 1280 KB Wrong Answer [6]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 1316 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 1312 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -