oj.uz

답안 #925671

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
925671 2024-02-12T07:18:19 Z daoquanglinh2007 Snowy Roads (JOI16_snowy) C++17
0 / 100
 18 ms 2144 KB 
#include "Anyalib.h"
#include <bits/stdc++.h>
using namespace std;

#define isz(a) (int)(a).size()

const int NM = 500, D = 11;

int N, A[NM+5], B[NM+5];
bool snow[NM+5];
vector <int> adj[NM+5], arr;
int parent[NM+5], dep[NM+5], f[NM+5], g[NM+5], dp[NM+5];

void dfs(int u, int p){
	parent[u] = p;
	dep[u] = (p == -1 ? 0 : dep[p]+1);
	f[u] = g[u] = dp[u] = 0;
	for (int v : adj[u]){
		if (v == p) continue;
		dfs(v, u);
		dp[u] += dp[v];
		if (f[v]+1 > f[u]){
			g[u] = f[u];
			f[u] = f[v]+1;
		}
		else if (f[v]+1 > g[u]){
			g[u] = f[v]+1;
		}
	}
	if (f[u]+g[u] > D){
		dp[u]++;
		arr.push_back(u);
		f[u] = g[u] = 0;
	}
}

void InitAnya(int _N, int _A[], int _B[]){
	N = _N;
	for (int i = 0; i < N-1; i++){
		A[i] = _A[i], B[i] = _B[i];
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
	arr.clear();
	dfs(0, -1);
	for (int i = 0; i < N-1; i++)
		if (dep[A[i]] > dep[B[i]]) swap(A[i], B[i]);
}

void Anya(int C[]){
	memset(snow, 0, sizeof(snow));
	for (int i = 0; i < N-1; i++)
		if (C[i]){
			snow[B[i]] = 1;
			Save(B[i], 1);
		}
	for (int i = 0; i < isz(arr); i++){
		int v = arr[i], cnt = 0;
		for (int u = v; u > 0; u = parent[u])
			if (snow[u]) cnt++;
		for (int j = 0; j <= 8; j++)
			Save(N+9*i+j, (cnt>>j)&1);
	}
}
#include "Borislib.h"
#include <bits/stdc++.h>
using namespace std;

#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair
#define isz(a) (int)(a).size()

const int NM = 500, LOG = 10, D = 11;

int N, A[NM+5], B[NM+5];
vector <int> adj[NM+5], arr;
int parent[NM+5], dep[NM+5], f[NM+5], g[NM+5], dp[NM+5];
int ecnt = 0, ap[NM+5];
pii sp[LOG+5][2*NM+5];

void dfs(int u, int p){
	parent[u] = p;
	dep[u] = (p == -1 ? 0 : dep[p]+1);
	ap[u] = ++ecnt;
	sp[0][ap[u]] = mp(dep[u], u);
	f[u] = g[u] = dp[u] = 0;
	for (int v : adj[u]){
		if (v == p) continue;
		dfs(v, u);
		sp[0][++ecnt] = mp(dep[u], u);
		dp[u] += dp[v];
		if (f[v]+1 > f[u]){
			g[u] = f[u];
			f[u] = f[v]+1;
		}
		else if (f[v]+1 > g[u]){
			g[u] = f[v]+1;
		}
	}
	if (f[u]+g[u] > D || (p == -1 && dp[u] == 0)){
		dp[u]++;
		arr.push_back(u);
		f[u] = g[u] = 0;
	}
}

void build_sparse(){
	for (int i = 1; i <= LOG; i++)
		for (int j = 1; j+(1<<i)-1 <= ecnt; j++)
			sp[i][j] = min(sp[i-1][j], sp[i-1][j+(1<<(i-1))]);
}

void InitBoris(int _N, int _A[], int _B[]){
	N = _N;
	for (int i = 0; i < N-1; i++){
		A[i] = _A[i], B[i] = _B[i];
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
	arr.clear();
	dfs(0, -1);
	for (int i = 0; i < N-1; i++)
		if (dep[A[i]] > dep[B[i]]) swap(A[i], B[i]);
	build_sparse();
}

int lca(int u, int v){
	int l = ap[u], r = ap[v];
	if (l > r) swap(l, r);
	int i = __lg(r-l+1);
	return min(sp[i][l], sp[i][r-(1<<i)+1]).se;
}

int dist(int u, int v){
	return dep[u]+dep[v]-2*dep[lca(u, v)];
}

int Boris(int v){
	int best = 0;
	for (int i = 1; i < isz(arr); i++){
		if (dist(v, arr[i]) < dist(v, arr[best])) best = i;
	}
	int ans = 0;
	for (int i = 0; i <= 8; i++)
		if (Ask(N+9*best+i)) ans += (1<<i);
		
	int u = arr[best], l = lca(u, v);
	while (u != l){
		if (Ask(u)) ans--;
		u = parent[u];
	}
	while (v != l){
		if (Ask(v)) ans++;
		v = parent[v];
	}
	return ans;
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 800 KB Output is correct
2 Correct 1 ms 808 KB Output is correct
3 Correct 2 ms 856 KB Output is correct
4 Correct 3 ms 1132 KB Output is correct
5 Correct 5 ms 1212 KB Output is correct
6 Correct 5 ms 1200 KB Output is correct
7 Correct 7 ms 1196 KB Output is correct
8 Correct 4 ms 1196 KB Output is correct
9 Incorrect 3 ms 1212 KB Wrong Answer [6]
10 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1244 KB Output is correct
2 Correct 5 ms 1232 KB Output is correct
3 Incorrect 4 ms 1252 KB Wrong Answer [6]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 18 ms 1848 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 2144 KB Output is correct
2 Incorrect 11 ms 1732 KB Wrong Answer [6]
3 Halted 0 ms 0 KB -