Submission #511085

# Submission time Handle Problem Language Result Execution time Memory
511085 2022-01-15T05:45:53 Z Register City (JOI17_city) C++14
Compilation error
0 ms 0 KB
#include <bits/stdc++.h>
#include "Encoder.h"
using namespace std;
const int N=(1<<18)+10,M=1<<8;
int n,tot,sz[N],dfi[N],dfo[N];
vector<int> e[N];
int id(int x) {return (x-1)/M;}
void dfs0(int x,int fa){
	sz[x]=1;
	for(int i=0;i<e[x].size();i++) if(e[x][i]==fa) {e[x].erase(e[x].begin()+i);break;}
	for(int y:e[x]) dfs0(y,x),sz[x]+=sz[y];
	sort(e[x].begin,e[x].end(),[&](const int&a,const&int b){return sz[a]<sz[b];});
}
void dfs1(int x,int fa){
	dfi[x]=++tot;
	for(int y:e[x]) dfs1(y,x);
	dfo[x]=tot;
	if(sz[x]>M){
		int k=id(dfo[x]);
		Code(x,(1<<27)+M*(k-1)*k/2+dfi[x]);
	}
}
void dfs2(int x,int fa,int ri){
	if(sz[x]>M) ri=id(dfo[x]);
	else Code(x,(ri==id(dfo[x]))<<26|dfi[x]<<8|(sz[x]-1));
	for(int y:e[x]) dfs2(y,x,ri);
}
void Encode(int nn,int u[],int v[]){
	n=nn;
	for(int i=0;i+1<n;i++) e[u[i]].push_back(v[i]),e[v[i]].push_back(u[i]);
	dfs0(0,-1);dfs1(0,-1);dfs2(0,-1,0);
}
#include <bits/stdc++.h>
#include "Device.h"
using namespace std;
const int M=256;
void InitDevice(){}
int id(int x) {return (x-1)/M;}
void calc(int&b,int&d,int&k,int x){
	if(x>>27&1){
		b=1;x-=(1<<27);k=0;
		int l=1,r=1000;
		while(l<=r){
			int mid=l+r>>1;
			if(M*mid*(mid-1)/2<x) k=mid,l=mid+1;
			else r=mid-1;
		}
		d=x-M*k*(k-1)/2;
	}else b=0,d=(x>>8),k=x-(d<<8);
}
int Answer(long long x,long long y){
	int s=x,t=y,bs,ds,ks,bt,dt,kt;
	calc(bs,ds,ks,s);calc(bt,dt,kt,t);
	if(bs&&bt){
		if(ds<dt&&kt<=ks) return 1;
		else if(dt<ds&&ks<=kt) return 0;
		return 2;
	}else if(!bs&&!bt){
		if(ds>>18&1) ds-=(1<<18);
		if(dt>>18&1) dt-=(1<<18);
		int rs=ds+ks,rt=dt+kt;
		if(ds<dt&&rt<=rs) return 1;
		else if(dt<ds&&rs<=rt) return 0;
		return 2;
	}else{
		bool fl=1,ri=0;
		if(bt) swap(ds,dt),swap(ks,kt),fl=0;
		if(dt>>18&1) ri=1,dt-=(1<<18);
		if(ds>dt||ks<id(dt+kt)) return 2;
		if(ks>id(dt+kt)||ri) return fl;
		return 2;
	}
}

Compilation message

Encoder.cpp: In function 'void dfs0(int, int)':
Encoder.cpp:10:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |  for(int i=0;i<e[x].size();i++) if(e[x][i]==fa) {e[x].erase(e[x].begin()+i);break;}
      |              ~^~~~~~~~~~~~
Encoder.cpp:12:50: error: ISO C++ forbids declaration of 'parameter' with no type [-fpermissive]
   12 |  sort(e[x].begin,e[x].end(),[&](const int&a,const&int b){return sz[a]<sz[b];});
      |                                                  ^
Encoder.cpp:12:51: error: expected ',' or '...' before 'int'
   12 |  sort(e[x].begin,e[x].end(),[&](const int&a,const&int b){return sz[a]<sz[b];});
      |                                                   ^~~
Encoder.cpp: In lambda function:
Encoder.cpp:12:74: error: 'b' was not declared in this scope
   12 |  sort(e[x].begin,e[x].end(),[&](const int&a,const&int b){return sz[a]<sz[b];});
      |                                                                          ^
Encoder.cpp: In function 'void dfs0(int, int)':
Encoder.cpp:12:78: error: no matching function for call to 'sort(<unresolved overloaded function type>, std::vector<int>::iterator, dfs0(int, int)::<lambda(const int&, const int&)>)'
   12 |  sort(e[x].begin,e[x].end(),[&](const int&a,const&int b){return sz[a]<sz[b];});
      |                                                                              ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from Encoder.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:4849:5: note: candidate: 'template<class _RAIter> void std::sort(_RAIter, _RAIter)'
 4849 |     sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~
/usr/include/c++/10/bits/stl_algo.h:4849:5: note:   template argument deduction/substitution failed:
Encoder.cpp:12:78: note:   candidate expects 2 arguments, 3 provided
   12 |  sort(e[x].begin,e[x].end(),[&](const int&a,const&int b){return sz[a]<sz[b];});
      |                                                                              ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from Encoder.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:4880:5: note: candidate: 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = dfs0(int, int)::<lambda(const int&, const int&)>]'
 4880 |     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
      |     ^~~~
/usr/include/c++/10/bits/stl_algo.h:4880:32: note:   no known conversion for argument 1 from '<unresolved overloaded function type>' to '__gnu_cxx::__normal_iterator<int*, std::vector<int> >'
 4880 |     sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
      |          ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~

Device.cpp: In function 'void calc(int&, int&, int&, int)':
Device.cpp:12:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   12 |    int mid=l+r>>1;
      |            ~^~