Submission #434162

#	Time	Username	Problem	Language	Result	Execution time	Memory
434162		mosiashvililuka	Handcrafted Gift (IOI20_gift)	C++14	0 / 100	1566 ms	54532 KiB

gift

#include "gift.h"
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,tes,t,msh[500009],f[500009],NO;
vector <int> v[500009];
string S;
pair <pair <int, int>, int> p[500009];
void mrg(int q, int w){
	q=msh[q];w=msh[w];
	if(q==w) return;
	if(v[q].size()<v[w].size()) swap(q,w);
	for(vector <int>::iterator it=v[w].begin(); it!=v[w].end(); it++){
		msh[(*it)]=q;
		v[q].push_back((*it));
	}
}
void mrg2(int q, int w){
	q=msh[q];w=msh[w];
	if(q==w){
		if(f[q]==f[w]){
			NO=1;return;
		}
		return;
	}
	if(v[q].size()<v[w].size()) swap(q,w);
	for(vector <int>::iterator it=v[w].begin(); it!=v[w].end(); it++){
		msh[(*it)]=q;
		f[(*it)]^=1;
	}
}
int construct(int Nn, int Rr, std::vector<int> Aa, std::vector<int> Bb, std::vector<int> Xx) {
	a=Nn;tes=Rr;
	for(t=1; t<=tes; t++){
		p[t].first.first=Aa[t-1]+1;p[t].first.second=Bb[t-1]+1;
		p[t].second=Xx[t-1];
	}
	for(i=1; i<=a; i++){
		msh[i]=i;f[i]=0;
		v[i].push_back(i);
	}
	sort(p+1,p+tes+1);
	zx=0;
	for(t=1; t<=tes; t++){
		if(p[t].second==2) continue;
		if(zx<p[t].first.first){
			zx=p[t].first.second;
			for(i=p[t].first.second; i>p[t].first.first; i--){
				mrg(i,i-1);
			}
		}else{
			for(i=p[t].first.second; i>zx; i--){
				mrg(i,i-1);
			}
		}
	}
	NO=0;
	for(t=1; t<=tes; t++){
		if(p[t].second==1) continue;
		mrg2(p[t].first.first,p[t].first.second);
		if(NO==1){
			return 0;
		}
	}
	for(i=1; i<=a; i++){
		if(f[i]==0){
			S+="R";
		}else{
			S+="B";
		}
	}
	craft(S);
	return 1;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 20
• Subtask 4: 0 / 25
• Subtask 5: 0 / 30