oj.uz

Submission #958329

# Submission time Handle Problem Language Result Execution time Memory
958329 2024-04-05T12:09:30 Z moonrabbit2 None (JOI12_invitation) C++17
100 / 100
 582 ms 101280 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 41664 KB Output is correct
2 Correct 12 ms 41564 KB Output is correct
3 Correct 12 ms 41664 KB Output is correct
4 Correct 13 ms 41660 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 41564 KB Output is correct
2 Correct 13 ms 41564 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 42076 KB Output is correct
2 Correct 16 ms 41820 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 42960 KB Output is correct
2 Correct 17 ms 43064 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 42964 KB Output is correct
2 Correct 16 ms 43220 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 582 ms 96752 KB Output is correct
2 Correct 125 ms 52544 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 95408 KB Output is correct
2 Correct 292 ms 97832 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 554 ms 97196 KB Output is correct
2 Correct 129 ms 53236 KB Output is correct
3 Correct 356 ms 88724 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 461 ms 92588 KB Output is correct
2 Correct 279 ms 101280 KB Output is correct
3 Correct 347 ms 74420 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 61348 KB Output is correct
2 Correct 512 ms 92840 KB Output is correct
3 Correct 436 ms 94544 KB Output is correct