답안 #61041

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
61041	2018-07-25T06:35:58 Z	윤교준(#1762)	City (JOI17_city)	C++11	8 / 100	532 ms	56936 KB

Encoder

#include "Encoder.h"
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define revv(V) reverse(allv(V))
#define sz(V) ((int)(V).size())
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
static void fg(vector<int> G[], int a, int b) { G[a].eb(b); G[b].eb(a); }

static const int MAXN = 250005;

static vector<int> G[MAXN];
static vector<int> V;

static int O[MAXN], C[MAXN];
static int A[MAXN], B[MAXN];

static int N;

static void dfs(int i, int &c) {
	c++; O[i] = c; C[i] = 1;
	for(int v : G[i]) if(!O[v]) {
		dfs(v, c);
		C[i] += C[v];
	}
	C[i] = *lower_bound(allv(V), C[i]);
	c = O[i] + C[i] - 1;
}

void Encode(int N, int A[], int B[]) {
	V.eb(1);
	for(int i = 2; i < (1<<20); i <<= 1) {
		V.eb(i);
		for(int j = i+1; j < (1<<20); j <<= 1)
			V.eb(j);
	}
	sorv(V); univ(V);

	::N = N;
	for(int i = 0; i < N-1; i++) {
		::A[i] = A[i];
		::B[i] = B[i];
		fg(G, A[i], B[i]);
	}

	{ int t = 0; dfs(0, t); }

	for(int i = 0; i < N; i++) {
		ll key = O[i]-1;
		key <<= 8;

		key |= int(lower_bound(allv(V), C[i]) - V.begin());

		Code(i, key);
	}
}

Device

#include "Device.h"
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define revv(V) reverse(allv(V))
#define sz(V) ((int)(V).size())
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

static vector<int> V;

void InitDevice() {
	V.eb(1);
	for(int i = 2; i < (1<<20); i <<= 1) {
		V.eb(i);
		for(int j = i+1; j < (1<<20); j <<= 1)
			V.eb(j);
	}
	sorv(V); univ(V);
}

int Answer(long long S, long long T) {
	int si = (S>>8), sc = S&((1<<8)-1);
	int ti = (T>>8), tc = T&((1<<8)-1);
	sc = V[sc]; tc = V[tc];

	if(ti < si && si < ti+tc) return 0;
	if(si < ti && ti < si+sc) return 1;
	return 2;
}

Subtask #1

8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	12544 KB	Output is correct
2	Correct	9 ms	12544 KB	Output is correct
3	Correct	7 ms	12288 KB	Output is correct
4	Correct	9 ms	12560 KB	Output is correct
5	Correct	8 ms	12536 KB	Output is correct
6	Correct	7 ms	12544 KB	Output is correct
7	Correct	8 ms	12288 KB	Output is correct
8	Correct	8 ms	12544 KB	Output is correct
9	Correct	8 ms	12544 KB	Output is correct
10	Correct	8 ms	12544 KB	Output is correct
11	Correct	8 ms	12288 KB	Output is correct
12	Correct	9 ms	12288 KB	Output is correct

Subtask #2

0 / 92.0

#	결과	실행 시간	메모리	Grader output
1	Correct	167 ms	19832 KB	Output is correct - L = 246784
2	Correct	166 ms	19536 KB	Output is correct - L = 302080
3	Correct	166 ms	19464 KB	Output is correct - L = 263424
4	Correct	169 ms	19440 KB	Output is correct - L = 350464
5	Correct	475 ms	55248 KB	Output is correct - L = 156080128
6	Correct	471 ms	55264 KB	Output is correct - L = 166030592
7	Correct	532 ms	55408 KB	Output is correct - L = 165107456
8	Correct	527 ms	54800 KB	Output is correct - L = 148158208
9	Correct	441 ms	56792 KB	Output is correct - L = 169719552
10	Correct	434 ms	56608 KB	Output is correct - L = 134271232
11	Correct	433 ms	56936 KB	Output is correct - L = 134217984
12	Correct	422 ms	56728 KB	Output is correct - L = 75499264
13	Incorrect	478 ms	55880 KB	Wrong Answer [6]
14	Halted	0 ms	0 KB	-