답안 #259708

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
259708	2020-08-08T11:29:40 Z	arnold518	Snowy Roads (JOI16_snowy)	C++14	100 / 100	24 ms	2128 KB

Anya
Boris

#include "Anyalib.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

static const int MAXN = 500;

static int N;
static vector<pii> adj[MAXN+10];
static pii E[MAXN+10];
static int C[MAXN+10], A[MAXN+10], B[MAXN+10], H[MAXN+10], par[MAXN+10];

static void dfs(int now, int bef, int d)
{
	A[now]=d;
	par[now]=bef;
	H[now]=0;
	for(auto nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		dfs(nxt.first, now, d+C[nxt.second]);
		H[now]=max(H[now], H[nxt.first]);
	}
	H[now]++;
	H[now]%=12;
}

void InitAnya(int _N, int A[], int B[])
{
	N=_N;
	for(int i=1; i<N; i++)
	{
		int u=A[i-1]+1, v=B[i-1]+1;
		adj[u].push_back({v, i});
		adj[v].push_back({u, i});
		E[i]={u, v};
	}
	dfs(1, 1, 0);
	for(int i=1; i<N; i++) if(par[E[i].first]==E[i].second) swap(E[i].first, E[i].second);
}

void Anya(int _C[])
{
	for(int i=1; i<N; i++)
	{
		C[i]=_C[i-1];
		B[E[i].second]=C[i];
	}
	dfs(1, 1, 0);
	for(int i=2; i<=N; i++) Save(i-2, B[i]);
	int cnt=0;
	for(int i=1; i<=N; i++)
	{
		if(H[i]) continue;
		for(int j=0; j<9; j++)
		{
			if(A[i]&(1<<j)) Save(N-1+cnt*9+j, 1);
			else Save(N-1+cnt*9+j, 0);
		}
		cnt++;
	}
}

#include "Borislib.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

static const int MAXN = 500;

static int N;
static vector<pii> adj[MAXN+10];
static pii E[MAXN+10];
static int C[MAXN+10], A[MAXN+10], B[MAXN+10], H[MAXN+10], par[MAXN+10];

static void dfs(int now, int bef, int d)
{
	A[now]=d;
	par[now]=bef;
	for(auto nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		dfs(nxt.first, now, d+C[nxt.second]);
		H[now]=max(H[now], H[nxt.first]);
	}
	H[now]++;
	H[now]%=12;
}

void InitBoris(int _N, int A[], int B[])
{
	N=_N;
	for(int i=1; i<N; i++)
	{
		int u=A[i-1]+1, v=B[i-1]+1;
		adj[u].push_back({v, i});
		adj[v].push_back({u, i});
		E[i]={u, v};
	}
	dfs(1, 1, 0);
	int cnt=0;
	for(int i=1; i<=N; i++) if(H[i]==0) B[i]=cnt++;
}

int Boris(int city)
{
	city++;
	int ret=0;

	int cnt=0;
	for(int i=1; i<=N; i++) if(H[i]==0) B[i]=cnt++;

	while(city!=1)
	{
		if(H[city]==0)
		{
			int t=0;
			for(int i=0; i<9; i++) t+=(Ask(N-1+B[city]*9+i)<<i);
			ret+=t;
			break;
		}
		else
		{
			int t=Ask(city-2);
			ret+=t;
			city=par[city];
		}
	}
	return ret;
}

Subtask #1
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	984 KB	Output is correct
2	Correct	1 ms	920 KB	Output is correct
3	Correct	3 ms	1212 KB	Output is correct
4	Correct	5 ms	1208 KB	Output is correct
5	Correct	7 ms	1432 KB	Output is correct
6	Correct	7 ms	1320 KB	Output is correct
7	Correct	8 ms	1428 KB	Output is correct
8	Correct	7 ms	1428 KB	Output is correct
9	Correct	8 ms	1320 KB	Output is correct
10	Correct	7 ms	1320 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	1552 KB	Output is correct
2	Correct	8 ms	1308 KB	Output is correct
3	Correct	9 ms	1436 KB	Output is correct
4	Correct	9 ms	1280 KB	Output is correct
5	Correct	9 ms	1424 KB	Output is correct
6	Correct	10 ms	1424 KB	Output is correct
7	Correct	9 ms	1424 KB	Output is correct
8	Correct	9 ms	1280 KB	Output is correct
9	Correct	9 ms	1304 KB	Output is correct
10	Correct	9 ms	1280 KB	Output is correct

Subtask #3
35.0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	20 ms	1888 KB	Output is correct
2	Correct	20 ms	1864 KB	Output is correct
3	Correct	20 ms	1892 KB	Output is correct
4	Correct	20 ms	1864 KB	Output is correct
5	Correct	23 ms	1864 KB	Output is correct
6	Correct	21 ms	1892 KB	Output is correct
7	Correct	20 ms	1792 KB	Output is correct
8	Correct	24 ms	1792 KB	Output is correct
9	Correct	21 ms	1792 KB	Output is correct
10	Correct	20 ms	1896 KB	Output is correct
11	Correct	21 ms	1896 KB	Output is correct
12	Correct	20 ms	1892 KB	Output is correct
13	Correct	22 ms	1864 KB	Output is correct
14	Correct	20 ms	1888 KB	Output is correct
15	Correct	20 ms	1864 KB	Output is correct
16	Correct	22 ms	1852 KB	Output is correct
17	Correct	22 ms	1864 KB	Output is correct
18	Correct	21 ms	1896 KB	Output is correct
19	Correct	20 ms	1864 KB	Output is correct
20	Correct	23 ms	1896 KB	Output is correct

Subtask #4
45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	1920 KB	Output is correct
2	Correct	19 ms	1860 KB	Output is correct
3	Correct	19 ms	1984 KB	Output is correct
4	Correct	19 ms	1904 KB	Output is correct
5	Correct	20 ms	1860 KB	Output is correct
6	Correct	18 ms	1792 KB	Output is correct
7	Correct	22 ms	1916 KB	Output is correct
8	Correct	18 ms	1792 KB	Output is correct
9	Correct	22 ms	1908 KB	Output is correct
10	Correct	20 ms	1924 KB	Output is correct
11	Correct	22 ms	1792 KB	Output is correct
12	Correct	18 ms	1924 KB	Output is correct
13	Correct	20 ms	1792 KB	Output is correct
14	Correct	20 ms	1860 KB	Output is correct
15	Correct	22 ms	1924 KB	Output is correct
16	Correct	18 ms	1796 KB	Output is correct
17	Correct	22 ms	1896 KB	Output is correct
18	Correct	20 ms	1860 KB	Output is correct
19	Correct	20 ms	1860 KB	Output is correct
20	Correct	20 ms	1912 KB	Output is correct
21	Correct	21 ms	1912 KB	Output is correct
22	Correct	24 ms	1912 KB	Output is correct
23	Correct	20 ms	1792 KB	Output is correct
24	Correct	20 ms	1860 KB	Output is correct
25	Correct	20 ms	1860 KB	Output is correct
26	Correct	20 ms	1860 KB	Output is correct
27	Correct	23 ms	1912 KB	Output is correct
28	Correct	20 ms	1908 KB	Output is correct
29	Correct	21 ms	1904 KB	Output is correct
30	Correct	20 ms	2128 KB	Output is correct
31	Correct	21 ms	2040 KB	Output is correct
32	Correct	18 ms	1932 KB	Output is correct
33	Correct	23 ms	1856 KB	Output is correct
34	Correct	19 ms	1928 KB	Output is correct
35	Correct	18 ms	1924 KB	Output is correct
36	Correct	20 ms	2028 KB	Output is correct
37	Correct	18 ms	1924 KB	Output is correct
38	Correct	21 ms	1860 KB	Output is correct
39	Correct	20 ms	1856 KB	Output is correct
40	Correct	20 ms	1792 KB	Output is correct
41	Correct	20 ms	1928 KB	Output is correct
42	Correct	20 ms	1856 KB	Output is correct
43	Correct	19 ms	1856 KB	Output is correct
44	Correct	17 ms	1856 KB	Output is correct
45	Correct	19 ms	1856 KB	Output is correct
46	Correct	18 ms	1948 KB	Output is correct
47	Correct	18 ms	1928 KB	Output is correct
48	Correct	18 ms	1972 KB	Output is correct
49	Correct	18 ms	1924 KB	Output is correct
50	Correct	18 ms	1792 KB	Output is correct

답안 #259708

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 5.0 / 5.0

Subtask #3 35.0 / 35.0

Subtask #4 45.0 / 45.0

Subtask #1
15.0 / 15.0

Subtask #2
5.0 / 5.0

Subtask #3
35.0 / 35.0

Subtask #4
45.0 / 45.0