oj.uz

Submission #1018568

# Submission time Handle Problem Language Result Execution time Memory
1018568 2024-07-10T06:56:02 Z pcc Ideal city (IOI12_city) C++17
0 / 100
 1000 ms 3676 KB 
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define fs first
#define sc second
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("popcnt,sse4")
#define ll long long

const int mod = 1e9;
const int mxn = 1e5+10;
vector<int> paths[mxn];
vector<pii> v;
int N;

ll mad(ll a,ll b){
	assert(a>=0&&b>=0);
	a %= mod;
	a += b;
	return a>=mod?a%mod:a;
}
ll mub(int a,int b){
	assert(a>=0&&b>=0);
	return mad(a,mod-b%mod);
}

namespace SUB1{
	int dist[mxn];
	queue<int> q;
	int BFS(int now){
		memset(dist,-1,sizeof(dist));
		dist[now] = 0;
		q.push(now);
		while(!q.empty()){
			auto now = q.front();
			q.pop();
			for(auto nxt:paths[now]){
				if(dist[nxt] == -1){
					dist[nxt] = dist[now]+1;
					q.push(nxt);
				}
			}
		}
		int re = 0;
		for(int i = 0;i<N;i++)re = (re+dist[i])%mod;
		return re;
	}
	int GO(int NN,int* xx,int *yy){
		N = NN;

		for(int i = 0;i<N;i++){
			v.push_back(pii(xx[i],yy[i]));
		}
		vector<int> perm;
		for(int i = 0;i<N;i++)perm.push_back(i);
		sort(perm.begin(),perm.end(),[](int a,int b){return v[a].fs == v[b].fs?v[a].sc<v[b].sc:v[a].fs<v[b].fs;});
		for(int i = 1;i<N;i++){
			int now = perm[i],pre = perm[i-1];
			if(v[now].fs == v[pre].fs&&v[now].sc == v[pre].sc+1){
				paths[now].push_back(pre);
				paths[pre].push_back(now);
			}
		}
		sort(perm.begin(),perm.end(),[](int a,int b){return v[a].sc == v[b].sc?v[a].fs<v[b].fs:v[a].sc<v[b].sc;});
		for(int i = 1;i<N;i++){
			int now = perm[i],pre = perm[i-1];
			if(v[now].sc == v[pre].sc&&v[now].fs == v[pre].fs+1){
				paths[now].push_back(pre);
				paths[pre].push_back(now);
			}
		}
		int ans = 0;
		for(int i = 0;i<N;i++){
			ans += BFS(i);
			ans %= mod;
		}
		assert(ans%2 == 0);
		return ans>>1;
	}
}

namespace SUB2{
	map<ll,ll> mx,my;
	int GO(int NN,int *X,int *Y){
		N = NN;

		{
			ll re = 0;
			for(int i = 0;i<N;i++){
				for(int j = i+1;j<N;j++){
					re += abs(X[i]-X[j])+abs(Y[i]-Y[j]);
					re %= mod;
				}
			}
			return re;
		}

		for(int i = 0;i<N;i++){
			mx[X[i]]++;
			my[Y[i]]++;
		}
		ll ans = 0;

		ll pref = 0,suf = 0,cnt = 0;
		for(auto &i:mx)suf = mad(suf,1ll*i.fs*i.sc%mod);
		for(auto &i:mx){
			auto t1 = mub(1ll*i.fs*cnt%mod,pref);
			auto t2 = mub(suf,1ll*i.fs*(N-cnt)%mod);
			t1 = 1ll*t1*i.sc%mod;t2 = 1ll*t2*i.sc%mod;
			ans = mad(ans,t1);ans = mad(ans,t2);
			pref = mad(pref,1ll*i.fs*i.sc%mod);
			cnt = mad(cnt,i.sc);
			suf = mub(suf,1ll*i.fs*i.sc%mod);
		}

		pref = suf = cnt = 0;
		for(auto &i:my)suf = mad(suf,1ll*i.fs*i.sc%mod);
		for(auto &i:my){
			auto t1 = mub(1ll*i.fs*cnt%mod,pref);
			auto t2 = mub(suf,1ll*i.fs*(N-cnt)%mod);
			t1 = 1ll*t1*i.sc%mod;t2 = 1ll*t2*i.sc%mod;
			ans = mad(ans,t1);ans = mad(ans,t2);
			pref = mad(pref,1ll*i.fs*i.sc%mod);
			cnt = mad(cnt,i.sc);
			suf = mub(suf,1ll*i.fs*i.sc%mod);
		}

		assert(ans%2 == 0);
		return ans>>1;
	}
}

int DistanceSum(int N, int *X, int *Y) {
	return SUB2::GO(N,X,Y);
	if(N<=2000)return SUB1::GO(N,X,Y);
	else return SUB2::GO(N,X,Y);
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 745 ms 3208 KB Output is correct
2 Correct 743 ms 3164 KB Output is correct
3 Execution timed out 1064 ms 3676 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

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