Submission #1010345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010345		ZeroCool	Ideal city (IOI12_city)	C++14	100 / 100	145 ms	23544 KiB

city

#include <bits/stdc++.h>

#define ar array
#define ll long long
#define int long long 	

using namespace std;

const int N = 1e5 + 20;
const int MOD = 1e9;
int ans = 0;
int X[N], Y[N];

int n;

set<int> g[N];
int w[N];

int p[N];
int sum[N];

int dfs(int x,int p){
	sum[x] = w[x];
	for(auto u: g[x]){
		if(u != p)sum[x] += dfs(u, x);
	}
	return sum[x];
}


void solve(){
	ar<int, 3> A[n];
	map<ar<int, 2>,int> mp;
	for(int i = 0;i < n;i++)A[i] = {X[i], Y[i], i}, mp[{X[i], Y[i]}] = i;
	sort(A, A+n);
	for(int i = 0;i < n;i++){
		g[i].clear();
		w[i] = 0;
		p[i] = 0;
		sum[i] = 0;
	}
	
	int cnt = 1;
	p[A[0][2]] = 0;
	w[0] = 1;
	
	
	for(int i = 1;i < n;i++){
		if(A[i][0] == A[i-1][0] && A[i][1] == A[i-1][1] + 1){
			w[p[A[i-1][2]]]++;
			p[A[i][2]] = p[A[i-1][2]];
		}else{
			w[cnt] = 1;
			p[A[i][2]] = cnt++;
		}
		if(mp.count({A[i][0] - 1, A[i][1]})){
			int u = p[A[i][2]];
			int v = p[mp[{A[i][0] - 1, A[i][1]}]];
			g[u].insert(v);
			g[v].insert(u);
		}
	}
	dfs(0, 0);
	int s = sum[0];
	for(int i = 0;i < n;i++){
		ans += (sum[i] * (s - sum[i])) % MOD;
		ans %= MOD;
	}
}

signed DistanceSum(signed _n, signed *x, signed *y) {
	n = _n;
	for(int i = 0;i<n;i++)X[i] = x[i], Y[i] = y[i];
	solve();
	for(int i = 0;i < n;i++)swap(X[i], Y[i]);
	solve();
	return ans;
  
}

#define int signed

Compilation message (stderr)

city.cpp:81: warning: "int" redefined
   81 | #define int signed
      | 
city.cpp:5: note: this is the location of the previous definition
    5 | #define int long long
      |

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45