oj.uz

Submission #73028

# Submission time Handle Problem Language Result Execution time Memory
73028 2018-08-27T13:53:16 Z IvanC None (JOI16_snowy) C++17
20 / 100
 23 ms 2176 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],necessaria[MAXN],pos_seq[MAXN];
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){
 
	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);
	}
 
}
 
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){
		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;
		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 = 0;
 
	dfs_build(0,-1);
	solve(0,-1,1,0);
	recover_dp(0,-1,1,0);
 
 	for(int i = 1;i<N;i++){
 		if(especial[i]) continue;
 		int liga = pai[i];
 		necessaria[liga] = 1;
 		pos_seq[liga] = lastPtr;
 		lastPtr++;
 	}

}
 
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++){
 		if(necessaria[i]) resposta[pos_seq[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],necessaria[MAXN],pos_seq[MAXN];
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){
 
	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);
	}
 
}
 
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){
		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;
		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(pos_seq[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 = 0;
 
	dfs_build(0,-1);
	solve(0,-1,1,0);
	recover_dp(0,-1,1,0);
 
 	for(int i = 1;i<N;i++){
 		if(especial[i]) continue;
 		int liga = pai[i];
 		necessaria[liga] = 1;
 		pos_seq[liga] = lastPtr;
 		lastPtr++;
 	}
 
}
 
int Boris(int city) {
	return doQuery(city);
}

Compilation message

Anya.cpp: In function 'void Anya(int*)':
Anya.cpp:117:40: warning: iteration 510 invokes undefined behavior [-Waggressive-loop-optimizations]
  for(int i = 0;i<1000;i++) resposta[i] = 0;
                            ~~~~~~~~~~~~^~~
Anya.cpp:117:17: note: within this loop
  for(int i = 0;i<1000;i++) resposta[i] = 0;
                ~^~~~~
Anya.cpp:126:38: warning: iteration 510 invokes undefined behavior [-Waggressive-loop-optimizations]
  for(int i = 0 ; i < 1000 ; i++) Save(i , resposta[i]);
                                  ~~~~^~~~~~~~~~~~~~~~~
Anya.cpp:126: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 5 ms 888 KB Output is correct
2 Correct 5 ms 1120 KB Output is correct
3 Correct 8 ms 1264 KB Output is correct
4 Correct 11 ms 1296 KB Output is correct
5 Correct 12 ms 1552 KB Output is correct
6 Correct 13 ms 1552 KB Output is correct
7 Correct 13 ms 1552 KB Output is correct
8 Correct 13 ms 1736 KB Output is correct
9 Correct 20 ms 1880 KB Output is correct
10 Correct 16 ms 1920 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
0 / 35.0

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

Subtask #4
0 / 45.0

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