Submission #1008923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008923		PenguinsAreCute	City (JOI17_city)	C++17	0 / 100	116 ms	25436 KiB

Encoder

#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
namespace {
	const int HALF = 125000;
	const int MAXN = 250000;
	ll enc(int a, int b) {
		if(!a) return b;
		assert(b<=2*a); assert(b>=a);
		if(a<HALF) {return ll(a)*(a+1)/2 + MAXN + 5 + (b-a);}
		a = MAXN - a;
		b = MAXN - b;
		return 7.813e9 + ll(a)*(a+1)/2+ b;
	}
	vector<int> adj[250005];
	int sub[250005];
	int dfs1(int x, int p) {
		sub[x]=1;
		for(auto i: adj[x]) if(i!=p) {sub[x]+=dfs1(i,x);}
		if(adj[x].size()>=3) {
			for(int i=1;i<adj[x].size();i++) if(adj[x][i]==p) swap(adj[x][i],adj[x][0]);
			for(int i=2;i<adj[x].size();i++) if(sub[adj[x][i]]>sub[adj[x][1]]) swap(adj[x][i],adj[x][1]);
		}
    return sub[x];
	}
	int pre[250005], post[250005], cnt;
	void dfs2(int x, int p) {
		pre[x]=cnt;
		for(auto i: adj[x]) if(i!=p) dfs2(i,x);
		post[x]=cnt++;
	}
}
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]);
	dfs1(0,-1); dfs2(0,-1);
	for (int i = 0; i < N; ++i) {
		Code(i, enc(pre[i],post[i]));
	}
}

Device

#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
namespace {
	const int HALF = 125000;
	const int MAXN = 250000;
	ll enc(int a, int b) {
		if(!a) return b;
		assert(b<=2*a); assert(b>=a);
		if(a<HALF) {return ll(a)*(a+1)/2 + MAXN + 5 + (b-a);}
		a = MAXN - a;
		b = MAXN - b;
		return 7.813e9 + ll(a)*(a+1)/2+ b;
	}
  pair<int,int> dec(ll x) {
    if(x<=MAXN) return {0,x};
    if(x<7.813e9) {
      ll hi = x - MAXN - 5;
      int l = 0, h = 250000;
      while(h-l>1) {
        int m = (l+h)/2;
        if(ll(m)*(m+1)/2 <= hi) l=m;
        else h=m;
      }
      return {l,hi - ll(l)*(l-1)/2};
    }
    // this problem tastes like complex bashing
    ll hi = x - 7.813e9;
    int l = 0, h = 250000;
    while(h-l>1) {
      int m = (l+h)/2;
      if(ll(m)*(m+1)/2 <= hi) l=m;
      else h=m;
    }
    return {MAXN-l,MAXN-(hi-ll(l)*(l+1)/2)};
  }
}

void InitDevice()
{
}

int Answer(long long S, long long T)
{
  pair<int,int> s = dec(S), t = dec(T);
  if(s.first<=t.first&&s.second>=t.second) return 1;
  if(t.first<=s.first&&t.second>=s.second) return 0;
  return 2;
}

Compilation message (stderr)

Encoder.cpp: In function 'int {anonymous}::dfs1(int, int)':
Encoder.cpp:22:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |    for(int i=1;i<adj[x].size();i++) if(adj[x][i]==p) swap(adj[x][i],adj[x][0]);
      |                ~^~~~~~~~~~~~~~
Encoder.cpp:23:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |    for(int i=2;i<adj[x].size();i++) if(sub[adj[x][i]]>sub[adj[x][1]]) swap(adj[x][i],adj[x][1]);
      |                ~^~~~~~~~~~~~~~

Device.cpp:8:5: warning: 'll {anonymous}::enc(int, int)' defined but not used [-Wunused-function]
    8 |  ll enc(int a, int b) {
      |     ^~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 92