| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 26183 |
2017-06-28T08:43:31 Z |
imsifile |
None (JOI16_snowy) |
C++ |
|
13 ms |
2900 KB |
#include "Anyalib.h"
#include <algorithm>
#include <vector>
#include <stdio.h>
#define rev(a) (reverse((a).begin(), (a).end()))
using namespace std;
struct HLD {
int root;
vector<int> v, e, bit; // edge count
vector<pair<int,int> > rng;
};
static int getL;
static int N, par[505], pedg[505], dy[505][2], chk[505];
static int hn_v[505][2];
static vector<int> con[505], edg[505];
static HLD hlds[505]; static int hcn;
static void make_BIT(int leng, int ix, int j2){
if(!j2 || leng<=ix) return;
if(leng >= ix+j2){
hlds[hcn].rng.push_back(make_pair(ix, ix+j2-1));
make_BIT(leng, ix+j2, j2/2);
}
make_BIT(leng, ix, j2/2);
}
static void HLD_info(int leaf, int r){
for(int i=leaf; i!=r; i=par[i]){
hlds[hcn].v.push_back(i);
hlds[hcn].e.push_back(pedg[i]);
hlds[hcn].bit.push_back(0);
chk[i]=1;
}
hlds[hcn].root = r;
rev(hlds[hcn].v), rev(hlds[hcn].e);
for(int i=hlds[hcn].v.size(); i--;){
int nod = hlds[hcn].v[i];
hn_v[nod][0]=hcn, hn_v[nod][1]=i;
}
make_BIT(hlds[hcn].e.size(), 0, 1024);
hcn++;
}
static void dfs(int ix){
dy[ix][1]=ix;
for(unsigned i=con[ix].size(); i--;){
int e=con[ix][i];
if(e==par[ix])continue;
par[e]=ix, pedg[e]=edg[ix][i], dfs(e);
if(dy[ix][0]<dy[e][0]+1) dy[ix][0]=dy[e][0]+1, dy[ix][1]=dy[e][1];
}
}
static void make_HLD(int ix){
for(unsigned i=con[ix].size(); i--;){
int e=con[ix][i];
if(e==par[ix])continue;
if(!chk[e]) HLD_info(dy[e][1], ix);
make_HLD(e);
}
}
void InitAnya(int N_ , int A[] , int B[]) {
N = N_;
for(int i=0; i<N-1; i++){
con[A[i]].push_back(B[i]);
edg[A[i]].push_back(i);
con[B[i]].push_back(A[i]);
edg[B[i]].push_back(i);
}
dfs(0);
make_HLD(0);
}
static int pcn;
static void bitify(int num, int mx){
int bits;
for(bits=0; mx>(1<<bits)-1; bits++);
for(int i=0; i<bits; i++){
if((1<<i) & num) Save(pcn++, 1);
else Save(pcn++, 0);
}
}
void Anya(int C[]) {
pcn=0;
for(int hn=0; hn<hcn; hn++){
for(int i=0; i<hlds[hn].rng.size(); i++){
int s=hlds[hn].rng[i].first, e=hlds[hn].rng[i].second;
hlds[hn].bit[i] = 0;
for(int j=s; j<=e; j++) hlds[hn].bit[i] += C[hlds[hn].e[j]];
bitify(hlds[hn].bit[i], e-s+1);
}
}
}
#include "Borislib.h"
#include <algorithm>
#include <vector>
#define rev(a) (reverse((a).begin(), (a).end()))
using namespace std;
struct HLD {
int root;
vector<int> v, e; // edge count
vector<pair<int,int> > rng, mem;
};
static int getL;
static int N, par[505], pedg[505], dy[505][2], chk[505];
static int hn_v[505][2];
static vector<int> con[505], edg[505];
static HLD hlds[505]; static int hcn;
static void make_BIT(int leng, int ix, int j2){
if(!j2 || leng<=ix) return;
if(leng >= ix+j2){
hlds[hcn].rng.push_back(make_pair(ix, ix+j2-1));
make_BIT(leng, ix+j2, j2/2);
}
make_BIT(leng, ix, j2/2);
}
static void HLD_info(int leaf, int r){
for(int i=leaf; i!=r; i=par[i]){
hlds[hcn].v.push_back(i);
hlds[hcn].e.push_back(pedg[i]);
chk[i]=1;
}
hlds[hcn].root = r;
rev(hlds[hcn].v), rev(hlds[hcn].e);
for(int i=hlds[hcn].v.size(); i--;){
int nod = hlds[hcn].v[i];
hn_v[nod][0]=hcn, hn_v[nod][1]=i;
}
make_BIT(hlds[hcn].e.size(), 0, 1024);
hcn++;
}
static void dfs(int ix){
dy[ix][1]=ix;
for(unsigned i=con[ix].size(); i--;){
int e=con[ix][i];
if(e==par[ix])continue;
par[e]=ix, pedg[e]=edg[ix][i], dfs(e);
if(dy[ix][0]<dy[e][0]+1) dy[ix][0]=dy[e][0]+1, dy[ix][1]=dy[e][1];
}
}
static void make_HLD(int ix){
for(unsigned i=con[ix].size(); i--;){
int e=con[ix][i];
if(e==par[ix])continue;
if(!chk[e]) HLD_info(dy[e][1], ix);
make_HLD(e);
}
}
static int pcn;
static int bitify(int mx){
int bits;
for(bits=0; mx>(1<<bits)-1; bits++);
return bits;
}
void InitBoris(int N_ , int A[] , int B[]) {
N = N_;
for(int i=0; i<N-1; i++){
con[A[i]].push_back(B[i]);
edg[A[i]].push_back(i);
con[B[i]].push_back(A[i]);
edg[B[i]].push_back(i);
}
dfs(0);
make_HLD(0);
for(int hn=0; hn<hcn; hn++){
for(int i=0; i<hlds[hn].rng.size(); i++){
int s=hlds[hn].rng[i].first, e=hlds[hn].rng[i].second;
int bb = bitify(e-s+1);
hlds[hn].mem.push_back(make_pair(pcn, pcn+bb-1));
pcn += bb;
}
}
hn_v[0][0]=-1;
}
int getsu(int hix, int ix){
int s = hlds[hix].mem[ix].first, e = hlds[hix].mem[ix].second;
int sum=0;
for(int i=s; i<=e; i++) sum |= (1<<(i-s)) * Ask(i);
return sum;
}
int getsum(int hix, int gas){
if(hix<0) return 0;
int s=0, e=gas, sum=0;
for(int i=0; i<hlds[hix].rng.size(); i++){
int ss=hlds[hix].rng[i].first, ee=hlds[hix].rng[i].second;
if(s==ss && ee<=e) sum+=getsu(hix, i), s=ee+1;
}
int r=hlds[hix].root;
return sum + getsum(hn_v[r][0], hn_v[r][1]);
}
int Boris(int city) {
return getsum(hn_v[city][0], hn_v[city][1]);
}
Compilation message
Anya.cpp: In function 'void Anya(int*)':
Anya.cpp:91:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<hlds[hn].rng.size(); i++){
^
Anya.cpp: At global scope:
Anya.cpp:14:12: warning: 'getL' defined but not used [-Wunused-variable]
static int getL;
^
Boris.cpp: In function 'void InitBoris(int, int*, int*)':
Boris.cpp:82:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<hlds[hn].rng.size(); i++){
^
Boris.cpp: In function 'int getsum(int, int)':
Boris.cpp:102:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<hlds[hix].rng.size(); i++){
^
Boris.cpp: At global scope:
Boris.cpp:13:12: warning: 'getL' defined but not used [-Wunused-variable]
static int getL;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2636 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2636 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2636 KB |
Output is correct |
| 5 |
Correct |
6 ms |
2636 KB |
Output is correct |
| 6 |
Correct |
3 ms |
2636 KB |
Output is correct |
| 7 |
Correct |
6 ms |
2636 KB |
Output is correct |
| 8 |
Correct |
3 ms |
2636 KB |
Output is correct |
| 9 |
Correct |
3 ms |
2636 KB |
Output is correct |
| 10 |
Correct |
3 ms |
2636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2636 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
2636 KB |
Wrong Answer [6] |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
2636 KB |
Wrong Answer [6] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
2900 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
2900 KB |
Wrong Answer [6] |
| 3 |
Halted |
0 ms |
0 KB |
- |
