oj.uz

Submission #61162

# Submission time Handle Problem Language Result Execution time Memory
61162 2018-07-25T09:40:32 Z ainta City (JOI17_city) C++17
100 / 100
 634 ms 110144 KB 
#include "Encoder.h"
#include<cstdio>
#include<algorithm>
#include<vector>
#include<map>
#define N_ 501000
using namespace std;
int TH = 127;
vector<int>E[N_],Ch[N_];
int C[N_], cnt, n, par[N_];

void DFS(int a, int pp) {
	C[a] = 1;
	par[a] = pp;
	for (auto &x : E[a]) {
		if (x == pp)continue;
		DFS(x, a);
		Ch[a].push_back(x);
		C[a] += C[x];
	}
}

int Num[N_], Num2[N_], Ed[N_], cc, PP[N_], Ed2[N_];

void DFS2(int a) {
	Num[a] = ++cc;
	for (auto &x : Ch[a]) {
		DFS2(x);
	}
	Ed[a] = cc;
}

void DFS3(int a) {
	Num[a] = ++cc;
	if (a >= n)return;
	for (auto &x : Ch[a]) {
		DFS3(x);
	}
	Ed[a] = cc;
}
void DFS4(int a, int pp) {
	PP[a] = pp;
	Num2[a] = ++cc;
	for (auto &x : Ch[a]) {
		DFS4(x, pp);
	}
	Ed2[a] = cc;
}

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);
	cnt = N - 1;
	int i, j;
	n = N;
	for (i = 0; i < N; i++) {
		if (C[i] >= TH) {
			int ck = 0, sss = 0;
			for (auto &x : Ch[i]) {
				if (C[x] < TH)sss = 1;
			}
			if (sss  == 0)continue;
			Ch[i].clear();
			for (auto &x : E[i]) {
				if (x != par[i] && C[x] >= TH)Ch[i].push_back(x);
			}
				vector<int>T;
				int s = 0;
				for (auto &x : E[i]) {
					if (C[x] >= TH)continue;
					if (s + C[x] >= TH) {
						++cnt;
						Ch[i].push_back(cnt);
						for (auto &y : T)Ch[cnt].push_back(y);
						s = 0;
						T.clear();
					}
					T.push_back(x);
					s += C[x];
				}
				++cnt;
				Ch[i].push_back(cnt);
				for (auto &y : T)Ch[cnt].push_back(y);
				s = 0;
				T.clear();
			}
	}
	if (cnt == N - 1) {
		DFS2(0);
	}
	else {
		cc = 0;
		DFS3(0);
		for (i = N; i <= cnt; i++) {
			cc = 0;
			DFS4(i,i);
			if (cc >= TH+1) {
				while (1) {}
			}
		}
	}
	for (i = 0; i < N; i++) {
		int r = 0;
		if (PP[i]) {
			r += (1 << 27);
			r += (Num[PP[i]] << 14);
			r += (Num2[i] << 7);
			r += Ed2[i];
		}
		else {
			r += (Num[i] << 13);
			r += Ed[i];
		}
		Code(i, r);
	}
}

#include "Device.h"

void InitDevice()
{
}

int Answer(long long S, long long T)
{
	int ck1 = (S >> 27), ck2 = (T >> 27);
	S &= ((1 << 27) - 1);
	T &= ((1 << 27) - 1);

	if (ck1 == 0 && ck2 == 0) {
		int bS = (S >> 13), eS = S & ((1 << 13) - 1);
		int bT = (T >> 13), eT = T & ((1 << 13) - 1);
		if (bS <= bT && eT <= eS)return 1;
		if (bT <= bS && eS <= eT)return 0;
		return 2;
	}
	else if (ck1 == 0 && ck2 == 1) {
		int bS = (S >> 13), eS = S & ((1 << 13) - 1);
		int TT = (T >> 14);
		if (bS <= TT && TT <= eS)return 1;
		return 2;
	}
	else if (ck1 == 1 && ck2 == 0) {
		int bS = (T >> 13), eS = T & ((1 << 13) - 1);
		int TT = (S >> 14);
		if (bS <= TT && TT <= eS)return 0;
		return 2;
	}
	else {
		if ((S >> 14) != (T >> 14))return 2;
		int ss = (S&((1 << 14) - 1));
		int tt = (T&((1 << 14) - 1));
		int bS = (ss >> 7), eS = (ss & 127);
		int bT = (tt >> 7), eT = (tt & 127);
		if (bS <= bT && eT <= eS)return 1;
		if (bT <= bS && eS <= eT)return 0;
		return 2;
	}
}

Compilation message

Encoder.cpp: In function 'void Encode(int, int*, int*)':
Encoder.cpp:62:8: warning: unused variable 'ck' [-Wunused-variable]
    int ck = 0, sss = 0;
        ^~
Encoder.cpp:58:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47872 KB Output is correct
2 Correct 24 ms 47872 KB Output is correct
3 Correct 21 ms 47872 KB Output is correct
4 Correct 23 ms 47744 KB Output is correct
5 Correct 23 ms 47872 KB Output is correct
6 Correct 23 ms 47872 KB Output is correct
7 Correct 22 ms 47872 KB Output is correct
8 Correct 25 ms 47864 KB Output is correct
9 Correct 24 ms 47840 KB Output is correct
10 Correct 23 ms 47872 KB Output is correct
11 Correct 23 ms 47872 KB Output is correct
12 Correct 23 ms 47872 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 54864 KB Output is correct - L = 134447749
2 Correct 190 ms 55024 KB Output is correct - L = 134450458
3 Correct 181 ms 54768 KB Output is correct - L = 134451232
4 Correct 181 ms 54768 KB Output is correct - L = 134479871
5 Correct 583 ms 108728 KB Output is correct - L = 221309782
6 Correct 585 ms 108832 KB Output is correct - L = 220419241
7 Correct 577 ms 108832 KB Output is correct - L = 221256631
8 Correct 587 ms 108056 KB Output is correct - L = 230227967
9 Correct 466 ms 104824 KB Output is correct - L = 172551643
10 Correct 476 ms 102464 KB Output is correct - L = 167456348
11 Correct 516 ms 102344 KB Output is correct - L = 167248130
12 Correct 474 ms 102288 KB Output is correct - L = 167231746
13 Correct 519 ms 106976 KB Output is correct - L = 190207403
14 Correct 558 ms 108376 KB Output is correct - L = 206918954
15 Correct 180 ms 54968 KB Output is correct - L = 134477420
16 Correct 185 ms 54768 KB Output is correct - L = 134520122
17 Correct 185 ms 54784 KB Output is correct - L = 134475872
18 Correct 556 ms 106472 KB Output is correct - L = 167346692
19 Correct 546 ms 107104 KB Output is correct - L = 167117058
20 Correct 534 ms 107120 KB Output is correct - L = 167033847
21 Correct 549 ms 105624 KB Output is correct - L = 169460615
22 Correct 591 ms 108240 KB Output is correct - L = 167049328
23 Correct 605 ms 108224 KB Output is correct - L = 167055263
24 Correct 582 ms 108936 KB Output is correct - L = 167301281
25 Correct 604 ms 109392 KB Output is correct - L = 167308763
26 Correct 582 ms 109848 KB Output is correct - L = 167254193
27 Correct 634 ms 110144 KB Output is correct - L = 167570649