oj.uz

Submission #61042

# Submission time Handle Problem Language Result Execution time Memory
61042 2018-07-25T06:41:24 Z ainta(#1756) City (JOI17_city) C++11
0 / 100
 173 ms 19584 KB 
#include "Encoder.h"
#include<cstdio>
#include<algorithm>
#include<vector>
#define N_ 251000
using namespace std;
vector<int>E[N_];
int L[N_];
int D[N_], Res[N_];

struct point {
	int l, x;
	bool operator<(const point &p)const {
		return l < p.l;
	}
};

void DFS(int a, int pp) {
	D[a] = L[a] = 0;
	for (auto &x : E[a]) {
		if (x == pp)continue;
		DFS(x, a);
	}
	vector<point>T;
	for (auto &x : E[a]) {
		if (x == pp)continue;
		T.push_back({ L[x],x });
	}
	if (T.empty()) return;
	if (T.size() == 1) {
		L[a] = T[0].l;
		return;
	}
	sort(T.begin(), T.end());
	long long s = 0;
	for (auto &t : T) {
		s += 1ll << t.l;
	}
	int i;
	for (i = 0;; i++) {
		if ((1ll << i) >= s)break;
	}
	L[a] = i;
	long long ss = 0;
	for (i = T.size() - 1; i >= 0; i--) {
		int x = T[i].x;
		int l = T[i].l;
		D[x] = (ss >> l);
		ss += (1ll << l);
	}
}
void Go(int a, int pp, long long g, int l) {
	Code(a, ((g << 1) + 1) << (L[0] - l));
	for (auto &x : E[a]) {
		if (x == pp)continue;
		Go(x, a, (g << (L[a] - L[x])) + D[x], l + L[a] - L[x]);
	}
}

void Encode(int N, int A[], int B[])
{
	for (int i = 0; i < N-1; ++i) {
		E[A[i]].push_back(B[i]);
		E[B[i]].push_back(A[i]);
	}
	DFS(0 ,-1);
	Go(0, -1, 0, 0);
}

#include "Device.h"

void InitDevice()
{
}

int Answer(long long S, long long T)
{
	int i, ck1 = 0, ck2 = 0;
	for (i = 0;i<60; i++) {
		if (ck1 && ck2 && ((S >> i) & 1) != ((T >> i) & 1))return 2;
		if (!ck1) {
			if ((S >> i) & 1)ck1 = i + 1;
		}
		if (!ck2) {
			if ((T >> i) & 1)ck2 = i + 1;
		}
	}
	if (ck1 < ck2)return 0;
	return 1;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 12544 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Incorrect 173 ms 19584 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -