oj.uz

답안 #413737

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
413737 2021-05-29T09:44:49 Z alishahali1382 City (JOI17_city) C++14
100 / 100
 583 ms 42828 KB 
#include "Encoder.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=1000000007;
const int MAXN=250002;

int n, m, k, u, v, SZ;
int stt[MAXN], fnt[MAXN], timer;
int par[MAXN], h[MAXN], sz[MAXN];
int shit[MAXN];
vector<int> G[MAXN];

int dfs1(int node){
	if (node){
		for (int &v:G[node]) if (v==par[node]) swap(v, G[node].back());
		G[node].pop_back();
	}
	sz[node]=1;
	for (int v:G[node]){
		par[v]=node;
		h[v]=h[node]+1;
		sz[node]+=dfs1(v);
	}
	return sz[node];
}
void dfs2(int node){
	stt[node]=timer++;
	sort(all(G[node]), [](int i, int j){
		return sz[i]>sz[j];
	});
	for (int v:G[node]) dfs2(v);
	fnt[node]=timer;
}

void Encode(int _n, int A[], int B[]){
	for (int i=0; i<800; i++) shit[SZ++]=i+1;
	ld eps=.05, val=shit[SZ-1];
	while (shit[SZ-1]<MAXN){
		val+=val*eps;
		// val+=log2(log2(val))*20;
		int x=val;
		if (x>MAXN) x=MAXN;
		if (x!=shit[SZ-1]) shit[SZ++]=x;
	}
	SZ=unique(shit, shit+SZ)-shit;
	debug(SZ)
	// fuck
	
	n=_n;
	for (int i=0; i<n-1; i++){
		u=A[i];
		v=B[i];
		G[u].pb(v);
		G[v].pb(u);
	}
	dfs1(0);
	dfs2(0);

	for (int i=0; i<n; i++){
		int szz=lower_bound(shit, shit+SZ, sz[i])-shit;
		Code(i, 1ll*szz*MAXN + stt[i]);
	}
}

#include "Device.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=1000000007;
const int MAXN=250002, LOG=60;

int Shit[MAXN], SZZ;

void InitDevice(){
	for (int i=0; i<800; i++) Shit[SZZ++]=i+1;
	ld eps=.05, val=Shit[SZZ-1];
	while (Shit[SZZ-1]<MAXN){
		val+=val*eps;
		// val+=log2(log2(val))*20;
		int x=val;
		if (x>MAXN) x=MAXN;
		if (x!=Shit[SZZ-1]) Shit[SZZ++]=x;
	}
	SZZ=unique(Shit, Shit+SZZ)-Shit;
	debug(SZZ)
	// fuck
}

int Answer(ll S, ll T){
	int szx=Shit[S/MAXN], sttx=S%MAXN, fntx=sttx+szx;
	int szy=Shit[T/MAXN], stty=T%MAXN, fnty=stty+szy;
	// debug2(sttx, fntx)
	// debug2(stty, fnty)
	if (stty<=sttx && sttx<fnty) return 0;
	if (sttx<=stty && stty<fntx) return 1;
	return 2;
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 6532 KB Output is correct
2 Correct 5 ms 6532 KB Output is correct
3 Correct 5 ms 6532 KB Output is correct
4 Correct 5 ms 6528 KB Output is correct
5 Correct 5 ms 6532 KB Output is correct
6 Correct 5 ms 6468 KB Output is correct
7 Correct 5 ms 6532 KB Output is correct
8 Correct 6 ms 6532 KB Output is correct
9 Correct 5 ms 6532 KB Output is correct
10 Correct 5 ms 6520 KB Output is correct
11 Correct 6 ms 6532 KB Output is correct
12 Correct 5 ms 6540 KB Output is correct

Subtask #2
92.0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Correct 199 ms 15188 KB Output is correct - L = 174751398
2 Correct 222 ms 15100 KB Output is correct - L = 174501396
3 Correct 195 ms 15068 KB Output is correct - L = 174751398
4 Correct 194 ms 15112 KB Output is correct - L = 174751398
5 Correct 534 ms 41988 KB Output is correct - L = 229251834
6 Correct 572 ms 42128 KB Output is correct - L = 229251834
7 Correct 517 ms 42068 KB Output is correct - L = 229251834
8 Correct 583 ms 41720 KB Output is correct - L = 229251834
9 Correct 449 ms 42744 KB Output is correct - L = 229251837
10 Correct 451 ms 42796 KB Output is correct - L = 229251851
11 Correct 453 ms 42708 KB Output is correct - L = 229251851
12 Correct 459 ms 42828 KB Output is correct - L = 229251851
13 Correct 571 ms 42388 KB Output is correct - L = 229251834
14 Correct 570 ms 42188 KB Output is correct - L = 229251834
15 Correct 192 ms 15064 KB Output is correct - L = 174751398
16 Correct 221 ms 15104 KB Output is correct - L = 174751398
17 Correct 193 ms 15088 KB Output is correct - L = 174751398
18 Correct 553 ms 42120 KB Output is correct - L = 229251850
19 Correct 512 ms 42272 KB Output is correct - L = 229251850
20 Correct 506 ms 42184 KB Output is correct - L = 229251850
21 Correct 579 ms 42288 KB Output is correct - L = 229251842
22 Correct 514 ms 42104 KB Output is correct - L = 229251849
23 Correct 542 ms 42156 KB Output is correct - L = 229251849
24 Correct 541 ms 42336 KB Output is correct - L = 229251848
25 Correct 542 ms 42140 KB Output is correct - L = 229251847
26 Correct 540 ms 42268 KB Output is correct - L = 229251846
27 Correct 538 ms 41944 KB Output is correct - L = 229251844