oj.uz

Submission #958327

# Submission time Handle Problem Language Result Execution time Memory
958327 2024-04-05T12:07:53 Z moonrabbit2 None (JOI12_invitation) C++17
50 / 100
 502 ms 89624 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=300005;
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<r){
			x[++sz[0]]=l+1;
			x[++sz[0]]=r;
		}
		y[++sz[1]]=s;
		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
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 29276 KB Output is correct
2 Correct 9 ms 29276 KB Output is correct
3 Correct 8 ms 29276 KB Output is correct
4 Incorrect 10 ms 29276 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 29276 KB Output is correct
2 Correct 10 ms 29276 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 29532 KB Output is correct
2 Correct 12 ms 29528 KB Output is correct

Subtask #4
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 30168 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 30236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 502 ms 85064 KB Output is correct
2 Correct 116 ms 42056 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 82088 KB Output is correct
2 Correct 231 ms 89624 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 84140 KB Output is correct
2 Correct 114 ms 42312 KB Output is correct
3 Correct 307 ms 64296 KB Output is correct

Subtask #9
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 398 ms 80040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 47748 KB Output is correct
2 Incorrect 375 ms 67504 KB Output isn't correct
3 Halted 0 ms 0 KB -