oj.uz

Submission #61116

# Submission time Handle Problem Language Result Execution time Memory
61116 2018-07-25T08:18:40 Z ainta(#1756) City (JOI17_city) C++11
100 / 100
 621 ms 110152 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 47856 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 47872 KB Output is correct
5 Correct 23 ms 47896 KB Output is correct
6 Correct 23 ms 47872 KB Output is correct
7 Correct 23 ms 47872 KB Output is correct
8 Correct 22 ms 47872 KB Output is correct
9 Correct 23 ms 47872 KB Output is correct
10 Correct 21 ms 47872 KB Output is correct
11 Correct 23 ms 47760 KB Output is correct
12 Correct 21 ms 47856 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 54784 KB Output is correct - L = 134447749
2 Correct 185 ms 54800 KB Output is correct - L = 134450458
3 Correct 186 ms 54768 KB Output is correct - L = 134451232
4 Correct 180 ms 54768 KB Output is correct - L = 134479871
5 Correct 586 ms 108856 KB Output is correct - L = 221309782
6 Correct 563 ms 108832 KB Output is correct - L = 220419241
7 Correct 583 ms 108872 KB Output is correct - L = 221256631
8 Correct 621 ms 107832 KB Output is correct - L = 230227967
9 Correct 485 ms 104536 KB Output is correct - L = 172551643
10 Correct 469 ms 102392 KB Output is correct - L = 167456348
11 Correct 455 ms 102296 KB Output is correct - L = 167248130
12 Correct 436 ms 102304 KB Output is correct - L = 167231746
13 Correct 519 ms 107080 KB Output is correct - L = 190207403
14 Correct 588 ms 107968 KB Output is correct - L = 206918954
15 Correct 185 ms 54912 KB Output is correct - L = 134477420
16 Correct 183 ms 54872 KB Output is correct - L = 134520122
17 Correct 180 ms 54968 KB Output is correct - L = 134475872
18 Correct 550 ms 106704 KB Output is correct - L = 167346692
19 Correct 564 ms 107464 KB Output is correct - L = 167117058
20 Correct 540 ms 107048 KB Output is correct - L = 167033847
21 Correct 552 ms 105496 KB Output is correct - L = 169460615
22 Correct 589 ms 108280 KB Output is correct - L = 167049328
23 Correct 593 ms 108424 KB Output is correct - L = 167055263
24 Correct 602 ms 108832 KB Output is correct - L = 167301281
25 Correct 595 ms 109272 KB Output is correct - L = 167308763
26 Correct 615 ms 109816 KB Output is correct - L = 167254193
27 Correct 605 ms 110152 KB Output is correct - L = 167570649