Submission #71370

#	Time	Username	Problem	Language	Result	Execution time	Memory
71370		krijgertje	Drzava (COCI15_drzava)	C++14	160 / 160	169 ms	29272 KiB

drzava

#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <cstring>
#include <list>  
#include <cassert>
#include <climits>
#include <chrono>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef unsigned long long ull;
typedef long long ll;  
int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }

struct P { int x,y,id; P():id(-1) {} P(int x,int y):x(x),y(y),id(-1) {} };
P operator-(const P &a,const P &b) { return P(a.x-b.x,a.y-b.y); }
ll operator^(const P &a,const P &b) { return (ll)a.x*b.y-(ll)a.y*b.x; }
ll side(const P &a,const P &b,const P &c) { return (b-a)^(c-a); }


void _mlt63(ull &a1,ull &a2) { // highest bits must be zero (so values less than 2^63)
	ull a1h=a1>>32,a1l=a1&((1ULL<<32)-1),a2h=a2>>32,a2l=a2&((1ULL<<32)-1);
	ull bh=a1h*a2h,bm=a1h*a2l+a1l*a2h,bl=a1l*a2l;
	bm+=bl>>32; bl&=(1ULL<<32)-1; bh=(bh<<1)+(bm>>31); bm&=(1ULL<<31)-1;
	a1=bh,a2=(bm<<32)+bl;
}
int _incirclecmp(ull a1,ull a2,ull b1,ull b2,ull c1,ull c2) { // highest bits must be zero (so values less than 2^63)
	_mlt63(a1,a2); _mlt63(b1,b2); _mlt63(c1,c2);
	a1+=b1; if((a2+=b2)>=(1ULL<<63)) a2-=1ULL<<63,++a1;
	return a1!=c1?a1<c1?-1:+1:a2!=c2?a2<c2?-1:+1:0;
}
bool incircle(const P &a,const P &b,const P &c,const P &d) { // whether d is in circumcenter of ccw triangle abc
	P aa=a-d,bb=b-d,cc=c-d;
	ll u1=(ll)aa.x*aa.x+(ll)aa.y*aa.y,u2=(ll)bb.x*cc.y-(ll)bb.y*cc.x;
	ll v1=(ll)bb.x*bb.x+(ll)bb.y*bb.y,v2=(ll)cc.x*aa.y-(ll)cc.y*aa.x;
	ll w1=(ll)cc.x*cc.x+(ll)cc.y*cc.y,w2=(ll)aa.x*bb.y-(ll)aa.y*bb.x;
	bool ret;
	if(u2>0) {
		if(v2>0) {
			if(w2>0) ret=true;
			else ret=_incirclecmp(u1,u2,v1,v2,w1,-w2)>0;
		} else {
			if(w2>0) ret=_incirclecmp(u1,u2,w1,w2,v1,-v2)>0;
			else ret=_incirclecmp(v1,-v2,w1,-w2,u1,u2)<0;
		}
	} else {
		if(v2>0) {
			if(w2>0) ret=_incirclecmp(v1,v2,w1,w2,u1,-u2)>0;
			else ret=_incirclecmp(u1,-u2,w1,-w2,v1,v2)<0;
		} else {
			if(w2>0) ret=_incirclecmp(u1,-u2,v1,-v2,w1,w2)<0;
			else ret=false;
		}
	}
	return ret;
}

bool operator<(const P &a,const P &b) { return a.x<b.x||a.x==b.x&&a.y<b.y; }
struct Delaunay {
	int n,m;
	vector<P> p;
	vector<int> gprv,gnxt,gto;
	void init(int _n) { n=_n,m=0; p=vector<P>(n); gprv.clear(),gnxt.clear(),gto.clear(); }
	void gotobottomhulledge(int &x,int &y) {
		while(gto[x]>gto[x^1]) x=gnxt[x]; while(gto[gprv[x]^1]>gto[gprv[x]]) x=gprv[x];
		while(gto[y]<gto[y^1]) y=gnxt[y]; while(gto[gprv[y]^1]<gto[gprv[y]]) y=gprv[y];
		while(true) {
			int a=gto[x^1],b=gto[y^1];
			if(side(p[a],p[b],p[gto[gprv[y]^1]])<0) y=gprv[y];
			else if(side(p[a],p[b],p[gto[x]])<0) x=gnxt[x];
			else break;
		}
	}
	int addedge(int a,int x,int b,int y) { // inserts a->b before a->x in a and before b->y in b
		//printf("addedge (%d,%d)-(%d,%d)\n",p[a].x,p[a].y,p[b].x,p[b].y);
		gprv.PB(gprv[x]),gnxt.PB(y),gto.PB(b);
		gprv.PB(gprv[y]),gnxt.PB(x),gto.PB(a);
		gnxt[gprv[m+0]]=m+0,gprv[gnxt[m+0]]=m+0,gnxt[gprv[m+1]]=m+1,gprv[gnxt[m+1]]=m+1;
		int ret=m; m+=2; return ret;
	}
	void remedge(int x) { // assumes not the last edge
		//int a=gto[x^1],b=gto[x]; printf("remedge (%d,%d)-(%d,%d)\n",p[a].x,p[a].y,p[b].x,p[b].y);
		gnxt[gprv[x]]=gnxt[x^1],gprv[gnxt[x]]=gprv[x^1];
		gnxt[gprv[x^1]]=gnxt[x],gprv[gnxt[x^1]]=gprv[x];
		gprv[x]=gnxt[x]=gto[x]=gprv[x^1]=gnxt[x^1]=gto[x^1]=-1;
	}
	int merge(int x,int y) {
		gotobottomhulledge(x,y);
		int a=gto[x^1],b=gto[y^1];
		//printf("bottom hull = (%d,%d)-(%d,%d)\n",p[a].x,p[a].y,p[b].x,p[b].y);
		x=addedge(a,x,b,y);
		while(true) {
			int ropt=-1,lopt=-1;
			while(true) {
				int y=gnxt[x],c=gto[y],d=gto[gnxt[y^1]];
				if(side(p[a],p[b],p[c])<=0) break;
				if(!incircle(p[a],p[b],p[c],p[d])) { ropt=c; break; }
				remedge(y);
			}
			while(true) {
				int y=gprv[x]^1,c=gto[y],d=gto[gprv[y]^1];
				if(side(p[a],p[b],p[c])<=0) break;
				if(!incircle(p[a],p[b],p[c],p[d])) { lopt=c; break; }
				remedge(y^1);
			}
			if(lopt!=-1&&(ropt==-1||!incircle(p[a],p[b],p[lopt],p[ropt]))) {
				x=addedge(lopt,gprv[x],b,gnxt[x]);
				a=lopt;
			} else if(ropt!=-1) {
				x=addedge(a,x,ropt,gnxt[gnxt[x]]);
				b=ropt;
			} else {
				return x;
			}
		}
	}
	int rec(int l,int r) {
		int cnt=r-l+1;
		if(cnt==2) {
			int a=l,b=l+1;
			gprv.PB(m+1),gnxt.PB(m+1),gto.PB(b);
			gprv.PB(m+0),gnxt.PB(m+0),gto.PB(a);
			int x=m+0; m+=2; return x;
		} else if(cnt==3) {
			int a=l,b=l+1,c=l+2; ll dir=side(p[a],p[b],p[c]); if(dir<0) swap(b,c),dir=-dir;
			gprv.PB(m+1),gnxt.PB(m+2),gto.PB(b);
			gprv.PB(m+3),gnxt.PB(m+0),gto.PB(a);
			gprv.PB(m+0),gnxt.PB(m+3),gto.PB(c);
			gprv.PB(m+2),gnxt.PB(m+1),gto.PB(b);
			int x=m+0,y=m+3; m+=4;
			if(dir>0) return addedge(a,x,c,y); else return x;
		} else {
			int m=l+(r-l)/2;
			int x=rec(l,m);
			int y=rec(m+1,r);
			return merge(x,y);
		}
	}
	int solve() {
		sort(p.begin(),p.end());
		return rec(0,n-1);
	}
	void print(int sx) {
		vector<int> state(m,0); queue<int> q; state[sx]=1,q.push(sx);
		while(!q.empty()) {
			int x=q.front(); q.pop(); if(state[x]==2) continue;
			vector<int> cur; while(state[x]!=2) { cur.PB(x); state[x]=2; x=gnxt[x]; }
			REPSZ(i,cur) { int id=gto[cur[i]^1]; printf("%d=(%d,%d) ",id,p[id].x,p[id].y); } puts("");
			REPSZ(i,cur) { int nx=cur[i]^1; if(state[nx]==0) state[nx]=1,q.push(nx); }
		}
	}
	void verify(int sx) {
		vector<bool> seen(m,false);
		REP(i,m) if(gto[i]!=-1&&!seen[i]) {
			vector<int> cur; int at=i; while(!seen[at]) { cur.PB(at); seen[at]=true; at=gnxt[at]; }
			if(SZ(cur)==3) {
				int a=gto[cur[0]],b=gto[cur[1]],c=gto[cur[2]];
				REP(j,n) assert(!incircle(p[a],p[b],p[c],p[j]));
			} else {
				bool found=false; REPSZ(j,cur) if(cur[j]==sx) found=true; assert(found);
			}
		}
	}
};

const int MAXN=50000;
int n,mod;
P p[MAXN];
int val[MAXN];

Delaunay delaunay;
vector<pair<ll,pair<int,int>>> opt;
ll calccost(const P &a,const P &b) { P d=b-a; return (ll)d.x*d.x+(ll)d.y*d.y; }

int ufpar[MAXN],ufsz[MAXN],ufmask[MAXN];
int uffind(int x) { if(ufpar[x]==x) return x; return ufpar[x]=uffind(ufpar[x]); }

void run() {
	scanf("%d%d",&n,&mod);
	REP(i,n) scanf("%d%d%d",&p[i].x,&p[i].y,&val[i]),p[i].id=i;

	delaunay.init(n);
	REP(i,n) delaunay.p[i]=p[i];
	int res=delaunay.solve();
	//delaunay.verify(res);
	//delaunay.print(res);

	opt.clear();
	REP(x,delaunay.m) if(x%2==0&&delaunay.gto[x]!=-1) { int a=delaunay.p[delaunay.gto[x^1]].id,b=delaunay.p[delaunay.gto[x]].id; opt.PB(MP(calccost(p[a],p[b]),MP(a,b)));  }
	sort(opt.begin(),opt.end());


	REP(i,n) ufpar[i]=i,ufsz[i]=i,ufmask[i]=1<<(val[i]%mod);
	REPSZ(i,opt) {
		int a=opt[i].second.first,b=opt[i].second.second;
		//printf("%d-%d = %lf\n",a,b,sqrt(1.0*opt[i].first));
		a=uffind(a),b=uffind(b); if(a==b) continue;
		if(ufsz[a]<ufsz[b]) swap(a,b);
		ufpar[b]=ufpar[a],ufsz[a]+=ufsz[b];
		int nmask=ufmask[a]|ufmask[b]; FOR(j,1,mod) if(ufmask[b]&(1<<j)) nmask|=((ufmask[a]&((1<<(mod-j))-1))<<j)|(ufmask[a]>>(mod-j)); ufmask[a]=nmask;
		if(ufmask[a]&(1<<0)) { printf("%.3lf\n",sqrt(1.0*opt[i].first)); return; }
	}
	assert(false);
}


int main() {
	//auto start_time = chrono::high_resolution_clock::now();
	run();
	//fprintf(stderr,"took %d us\n",chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now()-start_time).count());
	return 0;
}

Compilation message (stderr)

drzava.cpp: In function 'bool operator<(const P&, const P&)':
drzava.cpp:76:65: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
 bool operator<(const P &a,const P &b) { return a.x<b.x||a.x==b.x&&a.y<b.y; }
                                                         ~~~~~~~~^~~~~~~~~
drzava.cpp: In member function 'void Delaunay::gotobottomhulledge(int&, int&)':
drzava.cpp:83:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   while(gto[x]>gto[x^1]) x=gnxt[x]; while(gto[gprv[x]^1]>gto[gprv[x]]) x=gprv[x];
   ^~~~~
drzava.cpp:83:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   while(gto[x]>gto[x^1]) x=gnxt[x]; while(gto[gprv[x]^1]>gto[gprv[x]]) x=gprv[x];
                                     ^~~~~
drzava.cpp:84:3: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   while(gto[y]<gto[y^1]) y=gnxt[y]; while(gto[gprv[y]^1]<gto[gprv[y]]) y=gprv[y];
   ^~~~~
drzava.cpp:84:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   while(gto[y]<gto[y^1]) y=gnxt[y]; while(gto[gprv[y]^1]<gto[gprv[y]]) y=gprv[y];
                                     ^~~~~
drzava.cpp: In function 'void run()':
drzava.cpp:202:6: warning: unused variable 'res' [-Wunused-variable]
  int res=delaunay.solve();
      ^~~
drzava.cpp:197:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&mod);
  ~~~~~^~~~~~~~~~~~~~~~
drzava.cpp:198:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  REP(i,n) scanf("%d%d%d",&p[i].x,&p[i].y,&val[i]),p[i].id=i;
           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 8 / 8
• Subtask 5: 8 / 8
• Subtask 6: 8 / 8
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 8 / 8
• Subtask 13: 8 / 8
• Subtask 14: 8 / 8
• Subtask 15: 8 / 8
• Subtask 16: 8 / 8
• Subtask 17: 8 / 8
• Subtask 18: 8 / 8
• Subtask 19: 8 / 8
• Subtask 20: 8 / 8