oj.uz

Submission #73079

# Submission time Handle Problem Language Result Execution time Memory
73079 2018-08-27T15:11:11 Z IvanC None (JOI16_snowy) C++17
55 / 100
 28 ms 2376 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 int dp[MAXN][MOD][2];
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],nivel[MAXN];
 
static void dfs_build(int v,int p){
 
	for(int i : grafo[v]){
		int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
		if(u == p) continue;
		nivel[u] = nivel[v] + 1;
		pai[u] = i;
		dfs_build(u,v);
	}
 
}
 
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]);
	}
 
}
 
static int solve(int v,int p,int depth,int cor){
 
	if(dp[v][depth][cor] != -1) return dp[v][depth][cor];
 
	int tot = cor;
 
	for(int i : grafo[v]){
		int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
		if(u == p) continue;
		if(depth == 1){
			tot += solve(u,v,0,1);
		}
		else{
			tot += min(solve(u,v,depth+1,0), solve(u,v,0,1) );
		}
	}
 
	return dp[v][depth][cor] = tot;
 
}
 
static void recover_dp(int v,int p,int depth,int cor){
 
	if(cor == 1 && v != 0){
		int tam = 0;
		for(int i = 0;(1 << i) <= nivel[v];i++) tam = i + 1;
		especial[v] = 1;
		ini[v] = lastPtr;
		fim[v] = lastPtr + tam - 1;
		lastPtr += tam;
	}
 
	for(int i : grafo[v]){
		int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
		if(u == p) continue;
		if(depth == 11){
			recover_dp(u,v,0,1);
		}
		else{
			if(solve(u,v,depth+1,0) <= solve(u,v,0,1)) recover_dp(u,v,depth+1,0);
			else recover_dp(u,v,0,1);
		}
	}
 
}
 
void InitAnya(int n , int A[] , int B[]) {
 
	memset(dp,-1,sizeof(dp));
 
	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);
	solve(0,-1,1,0);
	recover_dp(0,-1,1,0);
 
	especial[0] = 0;
 
}
 
void Anya(int C[]){
	
	for(int i = 0;i<1000;i++) resposta[i] = 0;
	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 int dp[MAXN][MOD][2];
static vector<int> grafo[MAXN];
static int N,lastPtr,e1[MAXN],e2[MAXN];
static int pai[MAXN],especial[MAXN],ini[MAXN],fim[MAXN],nivel[MAXN];
 
static void dfs_build(int v,int p){
 
	for(int i : grafo[v]){
		int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
		if(u == p) continue;
		nivel[u] = nivel[v] + 1;
		pai[u] = i;
		dfs_build(u,v);
	}
 
}
 
static int solve(int v,int p,int depth,int cor){
 
	if(dp[v][depth][cor] != -1) return dp[v][depth][cor];
 
	int tot = cor;
 
	for(int i : grafo[v]){
		int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
		if(u == p) continue;
		if(depth == 1){
			tot += solve(u,v,0,1);
		}
		else{
			tot += min(solve(u,v,depth+1,0), solve(u,v,0,1) );
		}
	}
 
	return dp[v][depth][cor] = tot;
 
}
 
static void recover_dp(int v,int p,int depth,int cor){
 
	if(cor == 1 && v != 0){
		int tam = 0;
		for(int i = 0;(1 << i) <= nivel[v];i++) tam = i + 1;
		especial[v] = 1;
		ini[v] = lastPtr;
		fim[v] = lastPtr + tam - 1;
		lastPtr += tam;
	}
 
	for(int i : grafo[v]){
		int u = (e1[i] != v) ? (e1[i]) : (e2[i]);
		if(u == p) continue;
		if(depth == 11){
			recover_dp(u,v,0,1);
		}
		else{
			if(solve(u,v,depth+1,0) <= solve(u,v,0,1)) recover_dp(u,v,depth+1,0);
			else recover_dp(u,v,0,1);
		}
	}
 
}
 
static int doQuery(int v){
	
	if(v == 0) return 0;
 
	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[]) {
 
	memset(dp,-1,sizeof(dp));
 
	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);
	solve(0,-1,1,0);
	recover_dp(0,-1,1,0);
 
 
}
 
int Boris(int city) {
	return doQuery(city);
}

Compilation message

Anya.cpp: In function 'void Anya(int*)':
Anya.cpp:114:40: warning: iteration 510 invokes undefined behavior [-Waggressive-loop-optimizations]
  for(int i = 0;i<1000;i++) resposta[i] = 0;
                            ~~~~~~~~~~~~^~~
Anya.cpp:114:17: note: within this loop
  for(int i = 0;i<1000;i++) resposta[i] = 0;
                ~^~~~~
Anya.cpp:120:38: warning: iteration 510 invokes undefined behavior [-Waggressive-loop-optimizations]
  for(int i = 0 ; i < 1000 ; i++) Save(i , resposta[i]);
                                  ~~~~^~~~~~~~~~~~~~~~~
Anya.cpp:120: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 7 ms 892 KB Output is correct
2 Correct 5 ms 1032 KB Output is correct
3 Correct 8 ms 1240 KB Output is correct
4 Correct 11 ms 1360 KB Output is correct
5 Correct 13 ms 1560 KB Output is correct
6 Correct 15 ms 1992 KB Output is correct
7 Correct 13 ms 1992 KB Output is correct
8 Correct 16 ms 1992 KB Output is correct
9 Correct 13 ms 1992 KB Output is correct
10 Correct 14 ms 1992 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1992 KB Output is correct
2 Correct 13 ms 1992 KB Output is correct
3 Correct 17 ms 1992 KB Output is correct
4 Correct 16 ms 2024 KB Output is correct
5 Correct 13 ms 2024 KB Output is correct
6 Correct 13 ms 2024 KB Output is correct
7 Correct 13 ms 2024 KB Output is correct
8 Correct 13 ms 2024 KB Output is correct
9 Correct 17 ms 2024 KB Output is correct
10 Correct 21 ms 2024 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2176 KB Output is correct
2 Correct 23 ms 2212 KB Output is correct
3 Correct 24 ms 2248 KB Output is correct
4 Correct 22 ms 2248 KB Output is correct
5 Correct 23 ms 2248 KB Output is correct
6 Correct 21 ms 2248 KB Output is correct
7 Correct 23 ms 2248 KB Output is correct
8 Correct 22 ms 2248 KB Output is correct
9 Correct 24 ms 2248 KB Output is correct
10 Correct 25 ms 2248 KB Output is correct
11 Correct 22 ms 2252 KB Output is correct
12 Correct 22 ms 2256 KB Output is correct
13 Correct 27 ms 2256 KB Output is correct
14 Correct 28 ms 2256 KB Output is correct
15 Correct 23 ms 2256 KB Output is correct
16 Correct 22 ms 2256 KB Output is correct
17 Correct 22 ms 2288 KB Output is correct
18 Correct 24 ms 2376 KB Output is correct
19 Correct 27 ms 2376 KB Output is correct
20 Correct 24 ms 2376 KB Output is correct

Subtask #4
0 / 45.0

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