Submission #958329

#	Time	Username	Problem	Language	Result	Execution time	Memory
958329		moonrabbit2	초대 (JOI12_invitation)	C++17	100 / 100	582 ms	101280 KiB

invitation

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=array<int,2>;
using tii=array<int,3>;
using ti4=array<ll,4>;
using dat=array<int,5>;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
const int N=400005;
int n,m,s,k,x[N],y[N],sz[2],p[2*N];
multiset<int> S[2];
vector<int> add[2][N],del[2][N];
vector<dat> V;
vector<ti4> E;
ll ans;
int Find(int x){
	if(!p[x]) return x;
	return p[x]=Find(p[x]);
}
bool Union(int x,int y){
	x=Find(x); y=Find(y);
	if(x==y) return false;
	p[y]=x; return true;
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>m>>s>>k;
	V.resize(k);
	for(auto &[l,r,s,e,c]: V){
		cin>>l>>r>>s>>e>>c;
		x[++sz[0]]=l;
		if(l>1) x[++sz[0]]=l-1;
		if(l<r){
			x[++sz[0]]=l+1;
			x[++sz[0]]=r;
		}
		y[++sz[1]]=s;
		if(s>1) y[++sz[1]]=s-1;
		if(s<e){
			y[++sz[1]]=s+1;
			y[++sz[1]]=e;
		}
	}
	sort(x+1,x+1+sz[0]); sz[0]=unique(x+1,x+1+sz[0])-x-1;
	sort(y+1,y+1+sz[1]); sz[1]=unique(y+1,y+1+sz[1])-y-1;
	if(x[1]!=1||x[sz[0]]!=n||y[1]!=1||y[sz[1]]!=m){
		cout<<"-1\n";
		return 0;
	}
	for(auto [l,r,s,e,c]: V){
		l=lower_bound(x+1,x+1+sz[0],l)-x;
		r=lower_bound(x+1,x+1+sz[0],r)-x;
		s=lower_bound(y+1,y+1+sz[1],s)-y;
		e=lower_bound(y+1,y+1+sz[1],e)-y;
		add[0][l].push_back(c);
		del[0][r].push_back(c);
		add[1][s].push_back(c);
		del[1][e].push_back(c);
		E.push_back({c,c,l,sz[0]+s});
	}
	for(int t=0;t<2;t++){
		for(int i=1;i<sz[t];i++){
			for(int v: add[t][i]) S[t].insert(v);
			for(int v: del[t][i]) S[t].erase(S[t].lower_bound(v));
			if(S[t].size()) E.push_back({*S[t].rbegin(),(ll)(*S[t].rbegin())*(t==0?(x[i+1]-x[i]):(y[i+1]-y[i])),t*sz[0]+i,t*sz[0]+i+1});
		}
	}
	sort(E.begin(),E.end(),greater<>());
	debug(sz[0],sz[1],E);
	for(auto [c,cc,u,v]: E) if(Union(u,v)) ans+=cc;
	for(int i=2;i<=sz[0]+sz[1];i++) if(Find(1)!=Find(i)){
		cout<<"-1\n";
		return 0;
	}
	cout<<ans;
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10