oj.uz

Submission #61051

# Submission time Handle Problem Language Result Execution time Memory
61051 2018-07-25T07:00:32 Z ainta(#1756) City (JOI17_city) C++11
8 / 100
 586 ms 55656 KB 
#include "Encoder.h"
#include<cstdio>
#include<algorithm>
#include<vector>
#include<map>
#define N_ 251000
using namespace std;
vector<int>E[N_];
int L[N_];
int D[N_], Res[N_];
map<long long, int>Map;

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);
	}
}
int LM;
void Go(int a, int pp, long long g, int l, int dep) {
	Code(a, (((g << 1) + 1) << (L[0] - l)) * 32 + dep);
	for (auto &x : E[a]) {
		if (x == pp)continue;
		Go(x, a, (g << (L[a] - L[x])) + D[x], l + L[a] - L[x], dep+1);
	}
}

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, 0);
}

#include "Device.h"

void InitDevice()
{
}

int Answer(long long S, long long T)
{
	long long L1 = S & 31, L2 = T & 31;
	S >>= 5, T >>= 5;
	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;
	if (ck1 > ck2)return 1;
	if (L1 > L2)return 0;
	else return 1;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12544 KB Output is correct
2 Correct 16 ms 12544 KB Output is correct
3 Correct 8 ms 12544 KB Output is correct
4 Correct 9 ms 12544 KB Output is correct
5 Correct 7 ms 12544 KB Output is correct
6 Correct 9 ms 12544 KB Output is correct
7 Correct 8 ms 12544 KB Output is correct
8 Correct 9 ms 12544 KB Output is correct
9 Correct 8 ms 12544 KB Output is correct
10 Correct 7 ms 12488 KB Output is correct
11 Correct 8 ms 12544 KB Output is correct
12 Correct 8 ms 12544 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 19584 KB Output is correct - L = 139425
2 Correct 164 ms 19368 KB Output is correct - L = 262883
3 Correct 165 ms 19592 KB Output is correct - L = 225313
4 Correct 172 ms 19440 KB Output is correct - L = 24552
5 Partially correct 586 ms 55424 KB Output is partially correct - L = 1720264289
6 Partially correct 561 ms 55384 KB Output is partially correct - L = 1627720035
7 Partially correct 565 ms 55656 KB Output is partially correct - L = 2116374691
8 Correct 578 ms 54736 KB Output is correct - L = 8388593
9 Incorrect 181 ms 46128 KB Wrong Answer [3]
10 Halted 0 ms 0 KB -