oj.uz

Submission #73117

# Submission time Handle Problem Language Result Execution time Memory
73117 2018-08-27T16:49:00 Z IvanC None (JOI16_snowy) C++17
0 / 100
 5 ms 1336 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,resposta[MAXN],maioral[MAXN],custo[MAXN];
static int especial[MAXN],ini[MAXN],fim[MAXN],pai[MAXN]; 
static int e1[MAXN],e2[MAXN],distancia[MAXN];

static void dfs(int v,int p){

	maioral[v] = 0;

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

	if(maioral[v] == MOD){
		maioral[v] = 0;
		especial[v] = 1;
	}

}

static void dfs_bits(int v,int p,int depth){
	
	distancia[v] = depth;

	for(int i : grafo[v]){
		int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
		if(u == p) continue;
		dfs_bits(u,v,depth + 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(0,-1);
	especial[0] = 0;

	for(int i = 0;i<N;i++){
		if(especial[i]) continue;
		ini[i] = lastPtr;
		fim[i] = lastPtr + 8;
		lastPtr += 9;
	}

}
 
void Anya(int C[]){
	 
	 memset(resposta,0,sizeof(resposta));

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

	 dfs_bits(0,-1,0);

	 for(int i = 0;i<N;i++){
	 	if(!especial[i]) continue;
	 	for(int j = ini[i], k = 0;j<=fim[i];k++,j++){
	 		if(distancia[i] & (1 << k)) resposta[j] = 1;
	 		else resposta[j] = 0;
	 	}
	 }

	for(int i = 0 ; i < L_SZ ; i++) Save(i , resposta[i]);
 
}
#include "Borislib.h"
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 510;
const int MOD = 12;
 
static vector<int> grafo[MAXN];
static int N,lastPtr,maioral[MAXN];
static int especial[MAXN],ini[MAXN],fim[MAXN],pai[MAXN]; 
static int e1[MAXN],e2[MAXN];

static void dfs(int v,int p){

	maioral[v] = 0;

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

	if(maioral[v] == MOD){
		maioral[v] = 0;
		especial[v] = 1;
	}

}

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(0,-1);
	especial[0] = 0;

	for(int i = 0;i<N;i++){
		if(especial[i]) continue;
		ini[i] = lastPtr;
		fim[i] = lastPtr + 8;
		lastPtr += 9;
	}

}

static int doQuery(int v){

	if(v == 0) return 0;

	if(especial[v]){
		int tot = 0;
		for(int i = ini[v],j = 0;i <= fim[v];i++,j++){
			if(Ask(i)) tot += (1 << j);
		}
		return tot;
	}
	else{
		int i = pai[v];
		int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
		int x = doQuery(u), y = Ask(i);
		return x + y;
	}

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

Compilation message

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

Subtask #1
0 / 15.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 35.0

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

Subtask #4
0 / 45.0

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