oj.uz

Submission #72986

# Submission time Handle Problem Language Result Execution time Memory
72986 2018-08-27T12:10:52 Z IvanC None (JOI16_snowy) C++17
55 / 100
 858 ms 263168 KB 
#include "Anyalib.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 510;
const int L_SZ = 1000;
const int MOD = 12;

static vector<int> grafo[MAXN];
static int N,lastPtr,e1[MAXN],e2[MAXN],custo[MAXN];
static int resposta[MAXN],pai[MAXN],especial[MAXN],ini[MAXN],fim[MAXN];

static void dfs_build(int v,int p,int sp,int depth){

	if(depth % 12 == 0){
		sp = v;
		especial[v] = 1;
		ini[v] = lastPtr;
		fim[v] = lastPtr + 8;
		lastPtr += 9;
	}

	for(int i : grafo[v]){
		int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
		if(u == p) continue;
		pai[u] = i;
		dfs_build(u,v,sp,depth + 1);
	}

}

static void dfs_calculate(int v,int p,int dist){

	if(especial[v]){
		for(int i = ini[v], j = 0;i <= fim[v];i++,j++){
			if(dist & (1 << j)) resposta[i] = 1;
			else resposta[i] = 0;
		}
	}

	for(int i : grafo[v]){
		int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
		if(u == p) continue;
		dfs_calculate(u,v,dist + custo[i]);
	}

}

void InitAnya(int n , int A[] , int B[]) {

	N = n;

	for(int i = 0;i<N-1;i++){
		grafo[A[i]].push_back(i);
		grafo[B[i]].push_back(i);
		e1[i] = A[i];
		e2[i] = B[i];
	}

	lastPtr = N - 1;

	dfs_build(0,-1,-1,0);

}

void Anya(int C[]){
	
	for(int i = 0;i<N-1;i++) custo[i] = C[i]; 
	for(int i = 0;i<N-1;i++) resposta[i] = C[i]; 

	dfs_calculate(0,-1,0);

	for(int i = 0 ; i < 1000 ; i++) Save(i , resposta[i]);

}

#include "Borislib.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 510;
const int L_SZ = 1000;
const int MOD = 12;

static vector<int> grafo[MAXN];
static int N,lastPtr,e1[MAXN],e2[MAXN];
static int pai[MAXN],especial[MAXN],ini[MAXN],fim[MAXN];

static void dfs_build(int v,int p,int sp,int depth){

	if(depth % 12 == 0){
		sp = v;
		especial[v] = 1;
		ini[v] = lastPtr;
		fim[v] = lastPtr + 8;
		lastPtr += 9;
	}

	for(int i : grafo[v]){
		int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
		if(u == p) continue;
		pai[u] = i;
		dfs_build(u,v,sp,depth + 1);
	}

}

static int doQuery(int v){
	
	if(especial[v]){

		int numero = 0;

		for(int i = ini[v],j = 0;i <= fim[v];i++,j++){
			if(Ask(i)) numero += (1 << j);
		}

		return numero;

	}
	else{
		int i = pai[v];
		int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
		return Ask(i) + doQuery(u);
	}

}

void InitBoris(int n , int A[] , int B[]) {

	N = n;

	for(int i = 0;i<N-1;i++){
		grafo[A[i]].push_back(i);
		grafo[B[i]].push_back(i);
		e1[i] = A[i];
		e2[i] = B[i];
	}

	lastPtr = N - 1;

	dfs_build(0,-1,-1,0);

}

int Boris(int city) {
	return doQuery(city);
}

Compilation message

Anya.cpp: In function 'void Anya(int*)':
Anya.cpp:73:38: warning: iteration 510 invokes undefined behavior [-Waggressive-loop-optimizations]
  for(int i = 0 ; i < 1000 ; i++) Save(i , resposta[i]);
                                  ~~~~^~~~~~~~~~~~~~~~~
Anya.cpp:73:20: note: within this loop
  for(int i = 0 ; i < 1000 ; i++) Save(i , resposta[i]);
                  ~~^~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 768 KB Output is correct
2 Correct 7 ms 1120 KB Output is correct
3 Correct 10 ms 1624 KB Output is correct
4 Correct 13 ms 1776 KB Output is correct
5 Correct 17 ms 1896 KB Output is correct
6 Correct 19 ms 2192 KB Output is correct
7 Correct 16 ms 2192 KB Output is correct
8 Correct 17 ms 2268 KB Output is correct
9 Correct 17 ms 2288 KB Output is correct
10 Correct 18 ms 2288 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2344 KB Output is correct
2 Correct 17 ms 2600 KB Output is correct
3 Correct 19 ms 2600 KB Output is correct
4 Correct 18 ms 2600 KB Output is correct
5 Correct 18 ms 2656 KB Output is correct
6 Correct 18 ms 2768 KB Output is correct
7 Correct 17 ms 2888 KB Output is correct
8 Correct 18 ms 2992 KB Output is correct
9 Correct 20 ms 3104 KB Output is correct
10 Correct 19 ms 3184 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3328 KB Output is correct
2 Correct 31 ms 3840 KB Output is correct
3 Correct 29 ms 4392 KB Output is correct
4 Correct 30 ms 4864 KB Output is correct
5 Correct 32 ms 5496 KB Output is correct
6 Correct 31 ms 6016 KB Output is correct
7 Correct 24 ms 6400 KB Output is correct
8 Correct 32 ms 6912 KB Output is correct
9 Correct 24 ms 7424 KB Output is correct
10 Correct 30 ms 7936 KB Output is correct
11 Correct 28 ms 8560 KB Output is correct
12 Correct 28 ms 8960 KB Output is correct
13 Correct 26 ms 9472 KB Output is correct
14 Correct 25 ms 9984 KB Output is correct
15 Correct 24 ms 10496 KB Output is correct
16 Correct 26 ms 11008 KB Output is correct
17 Correct 22 ms 11520 KB Output is correct
18 Correct 23 ms 12032 KB Output is correct
19 Correct 26 ms 12544 KB Output is correct
20 Correct 23 ms 13056 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 858 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -