oj.uz

답안 #259705

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
259705 2020-08-08T11:12:03 Z arnold518 Snowy Roads (JOI16_snowy) C++14
15 / 100
 21 ms 1932 KB 
#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;

	while(city!=1)
	{
		if(H[city]==0)
		{
			for(int i=0; i<9; i++) ret+=(Ask(N-1+B[city]*9+i)<<i);
			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 988 KB Output is correct
2 Correct 2 ms 792 KB Output is correct
3 Correct 3 ms 1024 KB Output is correct
4 Correct 5 ms 1208 KB Output is correct
5 Correct 7 ms 1336 KB Output is correct
6 Correct 7 ms 1424 KB Output is correct
7 Correct 7 ms 1556 KB Output is correct
8 Correct 7 ms 1436 KB Output is correct
9 Correct 7 ms 1440 KB Output is correct
10 Correct 7 ms 1280 KB Output is correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1432 KB Output is correct
2 Incorrect 8 ms 1376 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

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

Subtask #4
0 / 45.0

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