Submission #67504

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
67504	2018-08-14T11:25:45 Z	reality	City (JOI17_city)	C++17	8 / 100	183 ms	57592 KB

Encoder

#include "Encoder.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define vii vector < pii >
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}

static const int N = 1e6;

static const db w = 1.045;

static int len[N];

static int wh[N];

vi g[N + 69];

static int T = -1;

void dfs(int node = 0,int prev = -1) {
	int beg = ++T;
	for (auto it : g[node])
		if (it != prev)
			dfs(it,node);
	int ln = T - beg;
	Code(node,1ll * wh[ln] * N + beg);
}


void Encode(int NN, int A[], int B[]) {
	int n = NN;
	for (int i = 0;i + 1 < n;++i) {
		g[A[i]].pb(B[i]);
		g[B[i]].pb(A[i]);
	}
	len[0] = 0;
	len[1] = 1;
	for (int i = 2;i < 256;++i)
		len[i] = max(len[i - 1] + 1,(int)(len[i - 1] * w));
	int j = 0;
	for (int i = 0;i < len[255];++i) {
		while (i > len[j])
			++j;
		wh[i] = j;
	}
	dfs();
}

Device

#include "Device.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define vii vector < pii >
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}

static const int N = 1e6;

static const db w = 1.045;

static int len[N];

static int wh[N];

void InitDevice() {
	len[0] = 0;
	len[1] = 1;
	for (int i = 2;i < 256;++i)
		len[i] = max(len[i - 1] + 1,(int)(len[i - 1] * w));
	int j = 0;
	for (int i = 0;i < len[255];++i) {
		while (i > len[j])
			++j;
		wh[i] = j;
	}
}

int Answer(ll S,ll T) {
	int a = S % N;
	int b = a + len[S / N];
	int c = T % N;
	int d = c + len[T / N];
	if (a <= c && d <= b)
		return 1;
	if (c <= a && b <= d)
		return 0;
	return 2;
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	50688 KB	Output is correct
2	Correct	24 ms	50432 KB	Output is correct
3	Correct	26 ms	50432 KB	Output is correct
4	Correct	23 ms	50424 KB	Output is correct
5	Correct	24 ms	50376 KB	Output is correct
6	Correct	23 ms	50432 KB	Output is correct
7	Correct	25 ms	50376 KB	Output is correct
8	Correct	24 ms	50432 KB	Output is correct
9	Correct	24 ms	50432 KB	Output is correct
10	Correct	25 ms	50432 KB	Output is correct
11	Correct	26 ms	50432 KB	Output is correct
12	Correct	25 ms	50416 KB	Output is correct

Subtask #2

0 / 92.0

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