Submission #26183

#	Time	Username	Problem	Language	Result	Execution time	Memory
26183		imsifile	Snowy Roads (JOI16_snowy)	C++98	15 / 100	13 ms	2900 KiB

Anya

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

Boris

#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 (stderr)

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;
            ^

• Subtask 1: 15 / 15
• Subtask 2: 0 / 5
• Subtask 3: 0 / 35
• Subtask 4: 0 / 45