Submission #733433

#	Time	Username	Problem	Language	Result	Execution time	Memory
733433		happypotato	Snowy Roads (JOI16_snowy)	C++17	100 / 100	24 ms	1924 KiB

Anya

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back

void Save(int place, int bit);

const int mxN = 1000;
int n;
vector<pii> edge;
 
vector<pair<int, pii>> adj[mxN]; // {node, {0/1, idx}}
int ans[mxN];
vector<int> key;
map<int, int> mp;
pii par[mxN];
int dfs(int u = 0, int pp = -1, int cur = 0) {
	ans[u] = cur;
	int res = 0;
	for (pair<int, pii> &v : adj[u]) {
		if (v.ff == pp) continue;
		par[v.ff] = {u, v.ss.ss};
		res = max(res, dfs(v.ff, u, cur + v.ss.ff) + 1);
	}
	if (res >= 10) {
		key.pb(u);
		res -= 10;
	}
	return res;
}
 
void InitAnya(int N, int A[], int B[]) {
	n = N;
	for (int i = 0; i < n - 1; i++) {
		edge.pb({A[i], B[i]});
	}
}
 
void Anya(int C[]) {
	for (int i = 0; i < n; i++) {
		adj[i].clear();
	}
	key.clear();
	for (int i = 0; i < n - 1; i++) {
		adj[edge[i].ff].pb({edge[i].ss, {C[i], i}});
		adj[edge[i].ss].pb({edge[i].ff, {C[i], i}});
	}
	dfs();
	for (int i = 0; i < n - 1; i++) {
		Save(500 + i, C[i]);
	}
	assert(key.size() <= 50);
	for (int i = 0; i < (int)(key.size()); i++) {
		for (int j = 0; j < 10; j++) {
			Save(i * 10 + j, bool(ans[key[i]] & (1 << j)));
		}
	}
}

Boris

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back

int Ask(int place);

const int mxN = 1000;
int n;
vector<pii> edge;
 
vector<pair<int, pii>> adj[mxN]; // {node, {0/1, idx}}
int ans[mxN];
vector<int> key;
map<int, int> mp;
pii par[mxN];
int dfs(int u = 0, int pp = -1, int cur = 0) {
	ans[u] = cur;
	int res = 0;
	for (pair<int, pii> &v : adj[u]) {
		if (v.ff == pp) continue;
		par[v.ff] = {u, v.ss.ss};
		res = max(res, dfs(v.ff, u, cur + v.ss.ff) + 1);
	}
	if (res >= 10) {
		key.pb(u);
		res -= 10;
	}
	return res;
}
 
void InitBoris(int N, int A[], int B[]) {
	n = N;
	for (int i = 0; i < n - 1; i++) {
		adj[A[i]].pb({B[i], {0, i}});
		adj[B[i]].pb({A[i], {0, i}});
	}
	dfs();
	mp[0] = -1;
	for (int i = 0; i < (int)(key.size()); i++) {
		mp[key[i]] = i;
	}
}
 
int Boris(int city) {
	int ans = 0;
	while (mp.find(city) == mp.end()) {
		ans += Ask(500 + par[city].ss);
		city = par[city].ff;
	}
	if (city) {
		for (int i = 0; i < 10; i++) {
			ans += (Ask(mp[city] * 10 + i) << i);
		}
	}
	return ans;
}

• Subtask 1: 15 / 15
• Subtask 2: 5 / 5
• Subtask 3: 35 / 35
• Subtask 4: 45 / 45