oj.uz

Submission #134105

# Submission time Handle Problem Language Result Execution time Memory
134105 2019-07-22T04:50:50 Z AngusRitossa City (JOI17_city) C++14
22 / 100
 681 ms 71048 KB 
#include "Encoder.h"
#include <bits/stdc++.h>
#ifdef DEBUG
	#define D(x...) printf(x)
#else	
	#define D(x...)
#endif
using namespace std;
typedef long long ll;
static vector<int> adj[250010];
static int seen[250010];
static int sz[250010];
int findsz(int a)
{
	if (sz[a]) return sz[a];
	sz[a] = 1;
	for (auto b : adj[a])
	{
		if (sz[b]) continue;
		sz[a] += findsz(b);
	}
	return sz[a];
}
void dfs(int a, ll node);
void dothing(int a, ll node, vector<pair<int, int> >& children)
{
	if (children.empty()) return;
	int sum = accumulate(children.begin(), children.end(), 0, [](const int &a, const pair<int, int> &b) { return a+b.first;});
	int am = 0;
	vector<pair<int, int> > after;
	for (int i = children.size()-1; i >= 0; i--)
	{
		after.push_back(children[i]);
		am += children[i].first;
	//	D("%d: here %d, %d, sum %d\n", a, am, i, sum);
		children.pop_back();
		if (am >= sum/2)
		{
			reverse(after.begin(), after.end());
			assert(children.size());
			if (children.size() == 1)
			{
				dfs(children[0].second, 2*node);
			}
			else dothing(a, 2*node, children);
			if (after.size() == 1) dfs(after[0].second, 2*node+1);
			else dothing(a, 2*node+1, after);
			return;
		}
	}
}
void dfs(int a, ll node)
{
	vector<pair<int, int> > children;
	seen[a] = 1;
	Code(a, node);
	D("%d: %lld\n", a, node);
	for (auto b : adj[a])
	{
		if (seen[b]) continue;
		children.push_back({sz[b], b});
	}
	sort(children.begin(), children.end());
	if (children.size() == 1) dfs(children[0].second, 2*node);
	else dothing(a, node, children);
}
void Encode(int n, int a[], int b[])
{
	for (int i = 0; i < n-1; i++)
	{
		adj[a[i]].push_back(b[i]);
		adj[b[i]].push_back(a[i]);
	}
	findsz(0);
	dfs(0, 1);
}

#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void InitDevice()
{

}
ll LOG2(ll a)
{
	int ans = 0;
	while (a)
	{
		ans++;
		a/=2;
	}
	return ans;
}
int Answer(ll s, ll t)
{
	int hei1 = LOG2(s);
	int hei2 = LOG2(t);
	int sbigger = hei1 < hei2;
	while (hei1 > hei2) hei1--, s/=2;
	while (hei1 < hei2) hei2--, t/=2;
	if (s == t) return sbigger;
	else return 2;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 26608 KB Output is correct - L = 118577
2 Correct 216 ms 26912 KB Output is correct - L = 1040032
3 Correct 222 ms 26608 KB Output is correct - L = 64058
4 Correct 204 ms 26608 KB Output is correct - L = 1023
5 Partially correct 635 ms 69104 KB Output is partially correct - L = 1067450362
6 Partially correct 645 ms 69152 KB Output is partially correct - L = 1073741561
7 Partially correct 618 ms 69104 KB Output is partially correct - L = 1064828925
8 Correct 611 ms 68512 KB Output is correct - L = 262143
9 Partially correct 636 ms 71048 KB Output is partially correct - L = 68719476733
10 Partially correct 586 ms 70944 KB Output is partially correct - L = 60129542141
11 Partially correct 563 ms 70880 KB Output is partially correct - L = 68685922301
12 Partially correct 568 ms 70824 KB Output is partially correct - L = 68291657725
13 Partially correct 614 ms 70072 KB Output is partially correct - L = 34359738365
14 Partially correct 624 ms 69696 KB Output is partially correct - L = 17179869181
15 Correct 215 ms 26608 KB Output is correct - L = 65534
16 Correct 212 ms 26680 KB Output is correct - L = 261884
17 Correct 208 ms 26752 KB Output is correct - L = 57330
18 Partially correct 621 ms 69848 KB Output is partially correct - L = 68306337789
19 Partially correct 631 ms 69616 KB Output is partially correct - L = 17181179903
20 Partially correct 679 ms 69672 KB Output is partially correct - L = 17180131327
21 Partially correct 681 ms 70960 KB Output is partially correct - L = 68719476733
22 Partially correct 668 ms 70888 KB Output is partially correct - L = 34360786881
23 Partially correct 665 ms 70936 KB Output is partially correct - L = 34360786881
24 Partially correct 651 ms 69760 KB Output is partially correct - L = 17180917745
25 Partially correct 665 ms 69552 KB Output is partially correct - L = 8590983165
26 Partially correct 652 ms 69664 KB Output is partially correct - L = 8592031729
27 Partially correct 669 ms 69280 KB Output is partially correct - L = 4299161593