Submission #427382

#	Time	Username	Problem	Language	Result	Execution time	Memory
427382		kai824	City (JOI17_city)	C++17	8 / 100	3072 ms	17740 KiB

Encoder

#include "Encoder.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> adjl[250005];
ll pre[250005],sub[250005],nex;

ll cnts[250005];
void init(){
	for(int i=1;i<250000;i++){
		cnts[i]=cnts[i-1]+(250000-i);
	}
}

ll convert(int x,int y){//returns no. of smaller pairs...
	y-=x;
	assert(cnts[x]+y<cnts[x+1]);
	return cnts[x]+y;
}

void dfs(int node,int p=-1){
	pre[node]=nex++;
	for(int x:adjl[node]){
		if(x==p)continue;
		dfs(x,node);
	}
	sub[node]=nex-1;
	// cout<<node<<' '<<pre[node]<<' '<<sub[node]<<'\n';
	Code(node,convert(pre[node],sub[node]));
}

void Encode(int n, int a[], int b[]){
	init();
	for(int i=0;i+1<n;i++){
		adjl[a[i]].push_back(b[i]);
		adjl[b[i]].push_back(a[i]);
	}
	dfs(0);
	//Code(i, 0LL): node, label...
}

Device

#include "Device.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll cnt[250005];
void InitDevice(){
	cnt[0]=0;
	for(int i=1;i<250000;i++){
		cnt[i]=cnt[i-1]+(250000-i);
	}
}
void unpack(ll x,int&a, int&b){
	for(int i=0;i<250000;i++){
		if(x>=cnt[i]){
			a=i;
			b=x-cnt[i];
		}
	}
	b+=a;
	//cout<<x<<' '<<a<<' '<<b<<'\n';
}

int Answer(long long s, long long t){
	int p1,p2,s1,s2;
	unpack(s,p1,s1);
	unpack(t,p2,s2);
	if(p1<p2 && p2<=s1)return 1;
	if(p2<p1 && p1<=s2)return 0;
	return 2;
}

Compilation message (stderr)

Device.cpp: In function 'int Answer(long long int, long long int)':
Device.cpp:20:3: warning: 's2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   20 |  b+=a;
      |  ~^~~
Device.cpp:25:15: note: 's2' was declared here
   25 |  int p1,p2,s1,s2;
      |               ^~
Device.cpp:29:2: warning: 'p2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   29 |  if(p2<p1 && p1<=s2)return 0;
      |  ^~
Device.cpp:20:3: warning: 's1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   20 |  b+=a;
      |  ~^~~
Device.cpp:25:12: note: 's1' was declared here
   25 |  int p1,p2,s1,s2;
      |            ^~
Device.cpp:29:2: warning: 'p1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   29 |  if(p2<p1 && p1<=s2)return 0;
      |  ^~

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