#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 = false;
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+9) return;
for(int i=1; i<=10; i++){
if( solve(last+i, nokori-c[last+i]) ){
v.insert(last+i);
hukugen(last+i, nokori-c[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 = false;
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+9) return;
for(int i=1; i<=10; i++){
if( solve(last+i, nokori-c[last+i]) ){
v.insert(last+i);
hukugen(last+i, nokori-c[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));
}
if(!solve(0,49)) cout << "Error" << endl;
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++){
~^~~~~~~~~~~~~~~~~~~
Boris.cpp: In function 'void InitBoris(int, int*, int*)':
Boris.cpp:59:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<tonari[now].size(); i++){
~^~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
912 KB |
Output is correct |
2 |
Correct |
5 ms |
836 KB |
Output is correct |
3 |
Correct |
7 ms |
1072 KB |
Output is correct |
4 |
Correct |
8 ms |
1024 KB |
Output is correct |
5 |
Correct |
11 ms |
1272 KB |
Output is correct |
6 |
Correct |
11 ms |
1280 KB |
Output is correct |
7 |
Correct |
10 ms |
1280 KB |
Output is correct |
8 |
Correct |
11 ms |
1404 KB |
Output is correct |
9 |
Correct |
13 ms |
1304 KB |
Output is correct |
10 |
Correct |
10 ms |
1500 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
1400 KB |
Output is correct |
2 |
Correct |
15 ms |
1480 KB |
Output is correct |
3 |
Correct |
18 ms |
1308 KB |
Output is correct |
4 |
Correct |
11 ms |
1044 KB |
Output is correct |
5 |
Correct |
12 ms |
1304 KB |
Output is correct |
6 |
Correct |
13 ms |
1308 KB |
Output is correct |
7 |
Correct |
13 ms |
1204 KB |
Output is correct |
8 |
Correct |
16 ms |
1172 KB |
Output is correct |
9 |
Correct |
17 ms |
1172 KB |
Output is correct |
10 |
Correct |
14 ms |
1300 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
1536 KB |
Output is correct |
2 |
Correct |
20 ms |
1332 KB |
Output is correct |
3 |
Correct |
27 ms |
1468 KB |
Output is correct |
4 |
Correct |
24 ms |
1332 KB |
Output is correct |
5 |
Correct |
22 ms |
1324 KB |
Output is correct |
6 |
Correct |
25 ms |
1340 KB |
Output is correct |
7 |
Correct |
22 ms |
1332 KB |
Output is correct |
8 |
Correct |
20 ms |
1340 KB |
Output is correct |
9 |
Correct |
20 ms |
1324 KB |
Output is correct |
10 |
Correct |
26 ms |
1332 KB |
Output is correct |
11 |
Correct |
26 ms |
1468 KB |
Output is correct |
12 |
Correct |
21 ms |
1536 KB |
Output is correct |
13 |
Correct |
32 ms |
1336 KB |
Output is correct |
14 |
Correct |
30 ms |
1336 KB |
Output is correct |
15 |
Correct |
24 ms |
1332 KB |
Output is correct |
16 |
Correct |
28 ms |
1368 KB |
Output is correct |
17 |
Correct |
25 ms |
1316 KB |
Output is correct |
18 |
Correct |
23 ms |
1280 KB |
Output is correct |
19 |
Correct |
21 ms |
1332 KB |
Output is correct |
20 |
Correct |
28 ms |
1324 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
1280 KB |
Output is correct |
2 |
Correct |
23 ms |
1520 KB |
Output is correct |
3 |
Correct |
20 ms |
1792 KB |
Output is correct |
4 |
Correct |
23 ms |
1792 KB |
Output is correct |
5 |
Correct |
25 ms |
1792 KB |
Output is correct |
6 |
Correct |
27 ms |
1856 KB |
Output is correct |
7 |
Correct |
20 ms |
1792 KB |
Output is correct |
8 |
Correct |
22 ms |
1804 KB |
Output is correct |
9 |
Correct |
23 ms |
1892 KB |
Output is correct |
10 |
Correct |
25 ms |
1856 KB |
Output is correct |
11 |
Correct |
23 ms |
1864 KB |
Output is correct |
12 |
Correct |
20 ms |
1936 KB |
Output is correct |
13 |
Correct |
27 ms |
1776 KB |
Output is correct |
14 |
Correct |
23 ms |
1868 KB |
Output is correct |
15 |
Correct |
22 ms |
1860 KB |
Output is correct |
16 |
Correct |
20 ms |
1872 KB |
Output is correct |
17 |
Correct |
23 ms |
1860 KB |
Output is correct |
18 |
Correct |
26 ms |
1860 KB |
Output is correct |
19 |
Correct |
27 ms |
1832 KB |
Output is correct |
20 |
Correct |
28 ms |
1896 KB |
Output is correct |
21 |
Correct |
32 ms |
1872 KB |
Output is correct |
22 |
Correct |
26 ms |
1864 KB |
Output is correct |
23 |
Correct |
26 ms |
1852 KB |
Output is correct |
24 |
Correct |
22 ms |
1820 KB |
Output is correct |
25 |
Correct |
24 ms |
1792 KB |
Output is correct |
26 |
Correct |
22 ms |
1868 KB |
Output is correct |
27 |
Correct |
21 ms |
1864 KB |
Output is correct |
28 |
Correct |
23 ms |
1864 KB |
Output is correct |
29 |
Correct |
23 ms |
1864 KB |
Output is correct |
30 |
Correct |
23 ms |
1856 KB |
Output is correct |
31 |
Correct |
22 ms |
1904 KB |
Output is correct |
32 |
Correct |
22 ms |
1792 KB |
Output is correct |
33 |
Correct |
26 ms |
1860 KB |
Output is correct |
34 |
Correct |
29 ms |
1900 KB |
Output is correct |
35 |
Correct |
20 ms |
1792 KB |
Output is correct |
36 |
Correct |
22 ms |
1868 KB |
Output is correct |
37 |
Correct |
22 ms |
2032 KB |
Output is correct |
38 |
Correct |
28 ms |
2048 KB |
Output is correct |
39 |
Correct |
18 ms |
1792 KB |
Output is correct |
40 |
Correct |
21 ms |
1848 KB |
Output is correct |
41 |
Correct |
21 ms |
1896 KB |
Output is correct |
42 |
Correct |
20 ms |
1944 KB |
Output is correct |
43 |
Correct |
22 ms |
2048 KB |
Output is correct |
44 |
Correct |
19 ms |
1792 KB |
Output is correct |
45 |
Correct |
20 ms |
1796 KB |
Output is correct |
46 |
Correct |
20 ms |
1892 KB |
Output is correct |
47 |
Correct |
23 ms |
1736 KB |
Output is correct |
48 |
Correct |
18 ms |
1904 KB |
Output is correct |
49 |
Correct |
21 ms |
1792 KB |
Output is correct |
50 |
Correct |
19 ms |
1792 KB |
Output is correct |