oj.uz

Submission #26095

# Submission time Handle Problem Language Result Execution time Memory
26095 2017-06-27T14:17:05 Z model_code None (JOI16_snowy) C++11
20 / 100
 19 ms 2728 KB 
#include "Anyalib.h"

static int getN;
static int getA[9999];
static int getB[9999];
static int getC[9999];
static int depth[9999];
static int parent[9999];
static int depthsum[99];
static int mindepth=0;
static int index[9999];
static void dfs(int now,int from,int curdepth) {
	depth[now]=curdepth;
	depthsum[curdepth%10]++;
	parent[now]=from;
	for(int i=0;i<getN-1;i++) {
		if(getA[i]==now) {
			if(getB[i]!=from) {
				dfs(getB[i],now,curdepth+1);
			}
		}
		if(getB[i]==now) {
			if(getA[i]!=from) {
				dfs(getA[i],now,curdepth+1);
			}
		}
	}
}
static void calcmin() {
	int mindepthvalue=getN;
	int i;
	for(i=0;i<10;i++) if(mindepthvalue>depthsum[i]) {
		mindepthvalue=depthsum[i];
		mindepth=i;
	}
}
void InitAnya(int N , int A[] , int B[]) {
	getN=N;
	for(int i=0;i<N-1;i++) {
		getA[i]=A[i];
		getB[i]=B[i];
	}
	dfs(0,-1,0);
	calcmin();
	int temp=0;
	int i;
	for(i=1;i<N;i++) {
		index[i]=temp;
		if(depth[i]%10==mindepth) {
			temp+=9;
		} else {
			temp++;
		}
	}
}
static void dfs2(int now,int from,int curdepth,int cursum,int prev) {
	if(now) {
		if(curdepth%10==mindepth) {
			int i;
			for(i=0;i<9;i++) {
				if(cursum&(1<<(8-i))) {
					Save(index[now]+i,1);
				} else {
					Save(index[now]+i,0);
				}
			}
		} else {
			Save(index[now],prev);
			Save(999-index[now],prev);
		}
	}
	for(int i=0;i<getN-1;i++) {
		if(getA[i]==now) {
			if(getB[i]!=from) {
				dfs2(getB[i],now,curdepth+1,cursum+getC[i],getC[i]);
			}
		}
		if(getB[i]==now) {
			if(getA[i]!=from) {
				dfs2(getA[i],now,curdepth+1,cursum+getC[i],getC[i]);
			}
		}
	}
}
void Anya(int C[]) {
	int i;
	for(i=0;i<getN-1;i++) getC[i]=C[i];
	dfs2(0,-1,0,0,-1);
}
#include <stdio.h>
#include "Borislib.h"

static int getN;
static int getA[9999];
static int getB[9999];
static int getC[9999];
static int depth[9999];
static int parent[9999];
static int depthsum[99];
static int mindepth=0;
static int index[9999];
static void dfs(int now,int from,int curdepth) {
	depth[now]=curdepth;
	depthsum[curdepth%10]++;
	parent[now]=from;
	for(int i=0;i<getN-1;i++) {
		if(getA[i]==now) {
			if(getB[i]!=from) {
				dfs(getB[i],now,curdepth+1);
			}
		}
		if(getB[i]==now) {
			if(getA[i]!=from) {
				dfs(getA[i],now,curdepth+1);
			}
		}
	}
}
static void calcmin() {
	int mindepthvalue=getN;
	int i;
	for(i=0;i<10;i++) if(mindepthvalue>depthsum[i]) {
		mindepthvalue=depthsum[i];
		mindepth=i;
	}
}
void InitBoris(int N , int A[] , int B[]) {
	getN=N;
	for(int i=0;i<N-1;i++) {
		getA[i]=A[i];
		getB[i]=B[i];
	}
	dfs(0,-1,0);
	calcmin();
	int temp=0;
	int i;
	for(i=1;i<N;i++) {
		index[i]=temp;
		if(depth[i]%10==mindepth) {
			temp+=9;
		} else {
			temp++;
		}
	}
}
int Boris(int city) {
	int sol=0;
	int solx=0;
	int i;
	while(depth[city]%10!=mindepth) {
		if(city==0) break;
		sol+=Ask(index[city]);
		city=parent[city];
	}
	if(city) {
		for(i=0;i<9;i++) solx = solx*2 + Ask(index[city]+i);
	}
	if(sol+solx>=getN) return getN-1;
	return sol+solx;
}

Compilation message

Boris.cpp:7:12: warning: 'getC' defined but not used [-Wunused-variable]
 static int getC[9999];
            ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2728 KB Output is correct
2 Correct 0 ms 2728 KB Output is correct
3 Correct 0 ms 2728 KB Output is correct
4 Correct 0 ms 2728 KB Output is correct
5 Correct 6 ms 2728 KB Output is correct
6 Correct 6 ms 2728 KB Output is correct
7 Correct 3 ms 2728 KB Output is correct
8 Correct 6 ms 2728 KB Output is correct
9 Correct 3 ms 2728 KB Output is correct
10 Correct 3 ms 2728 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2728 KB Output is correct
2 Correct 12 ms 2728 KB Output is correct
3 Correct 13 ms 2728 KB Output is correct
4 Correct 16 ms 2728 KB Output is correct
5 Correct 12 ms 2728 KB Output is correct
6 Correct 12 ms 2728 KB Output is correct
7 Correct 9 ms 2728 KB Output is correct
8 Correct 9 ms 2728 KB Output is correct
9 Correct 19 ms 2728 KB Output is correct
10 Correct 16 ms 2728 KB Output is correct

Subtask #3
0 / 35.0

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

Subtask #4
0 / 45.0

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