oj.uz

답안 #284405

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
284405 2020-08-27T11:07:43 Z amiratou 이상적인 도시 (IOI12_city) C++14
100 / 100
 87 ms 13560 KB 
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h> 
using namespace std;
#define fi first
#define se second
typedef long long ll ;
#define sz(x) (ll)(x.size())
const ll MOD = (ll)(1e9),MX=(int)(1e5+5);
typedef pair<ll,ll> ii;

int par[MX];
ll ans,cnt[MX],comp,cl[MX];
vector<pair<int,ii> > vec[MX];
vector<ii> vecD[2];

ii solve(ll node,ll p){
	ii h={0,cnt[node]};
	for(auto &it:vec[node])
		if(it.fi!=p){
			if(it.se.fi==-1)
				it.se=solve(it.fi,node);
			h.fi+=it.se.fi+it.se.se;
			h.se+=it.se.se;
		}
	return h;
}
ll findSetXY(ll i){
	if(par[i]==i)return i;
	return par[i]=findSetXY(par[i]);
}
bool UnionXY(ll a,ll b){
	ll x=findSetXY(a),y=findSetXY(b);
	if(x!=y){par[x]=y;return 1;}
	return 0;
}
void work(ll idx){
	comp=0;
	for (int i = 0; i < sz(vecD[idx]); ++i)
		par[i]=i,cnt[i]=0,vec[i].clear();
	for (int i = 0; i < sz(vecD[idx]);)
	{
		int j=i;
		while(j<sz(vecD[idx]) && vecD[idx][j].fi==vecD[idx][i].fi && (vecD[idx][i].se+(j-i))==vecD[idx][j].se){
			cl[j]=comp;
			ll k=lower_bound(vecD[idx].begin(),vecD[idx].end(),make_pair(vecD[idx][j].fi-1,vecD[idx][j].se))-vecD[idx].begin();
			if(k!=sz(vecD[idx]) && vecD[idx][k]==make_pair(vecD[idx][j].fi-1,vecD[idx][j].se)){
				ll a=cl[j],b=cl[k];
				if(UnionXY(a,b)){vec[a].push_back({b,{-1,-1}}),vec[b].push_back({a,{-1,-1}});}
			}
			cnt[cl[j]]++,j++;
		}
		comp++,i=j;
	}
	for (int i = 0; i < comp; ++i)
		ans+=solve(i,i).fi*cnt[i];
}

int DistanceSum(int N, int *X, int *Y) {
	vecD[0].resize(N),vecD[1].resize(N);
	for (ll i = 0; i < N; ++i)
		vecD[0][i]={X[i],Y[i]},vecD[1][i]={Y[i],X[i]};
	for (ll i = 0; i < 2; ++i)
		sort(vecD[i].begin(),vecD[i].end());
	work(0),work(1);
	return (ans>>1LL)%MOD;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2816 KB Output is correct
2 Correct 3 ms 2816 KB Output is correct
3 Correct 3 ms 2816 KB Output is correct
4 Correct 3 ms 2816 KB Output is correct
5 Correct 4 ms 2816 KB Output is correct
6 Correct 3 ms 2816 KB Output is correct
7 Correct 4 ms 2944 KB Output is correct
8 Correct 3 ms 2816 KB Output is correct
9 Correct 3 ms 2816 KB Output is correct
10 Correct 3 ms 2816 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 3968 KB Output is correct
2 Correct 13 ms 3968 KB Output is correct
3 Correct 31 ms 5752 KB Output is correct
4 Correct 33 ms 5888 KB Output is correct
5 Correct 61 ms 8696 KB Output is correct
6 Correct 67 ms 8876 KB Output is correct
7 Correct 67 ms 8824 KB Output is correct
8 Correct 66 ms 8824 KB Output is correct
9 Correct 62 ms 9080 KB Output is correct
10 Correct 65 ms 13560 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 4608 KB Output is correct
2 Correct 16 ms 4480 KB Output is correct
3 Correct 41 ms 7416 KB Output is correct
4 Correct 38 ms 6904 KB Output is correct
5 Correct 83 ms 12024 KB Output is correct
6 Correct 73 ms 10104 KB Output is correct
7 Correct 87 ms 12152 KB Output is correct
8 Correct 72 ms 10104 KB Output is correct
9 Correct 68 ms 9464 KB Output is correct
10 Correct 67 ms 9496 KB Output is correct