oj.uz

Submission #1010345

# Submission time Handle Problem Language Result Execution time Memory
1010345 2024-06-28T21:18:14 Z ZeroCool Ideal city (IOI12_city) C++14
100 / 100
 145 ms 23544 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5208 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 3 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 3 ms 4956 KB Output is correct
10 Correct 2 ms 5192 KB Output is correct
11 Correct 3 ms 4956 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5212 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 3 ms 5212 KB Output is correct
4 Correct 3 ms 5212 KB Output is correct
5 Correct 3 ms 5468 KB Output is correct
6 Correct 3 ms 5468 KB Output is correct
7 Correct 4 ms 5548 KB Output is correct
8 Correct 3 ms 5392 KB Output is correct
9 Correct 3 ms 5468 KB Output is correct
10 Correct 6 ms 5412 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 8028 KB Output is correct
2 Correct 22 ms 8028 KB Output is correct
3 Correct 59 ms 12124 KB Output is correct
4 Correct 52 ms 12380 KB Output is correct
5 Correct 118 ms 19540 KB Output is correct
6 Correct 108 ms 19360 KB Output is correct
7 Correct 121 ms 19536 KB Output is correct
8 Correct 105 ms 19024 KB Output is correct
9 Correct 111 ms 19516 KB Output is correct
10 Correct 106 ms 23544 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8796 KB Output is correct
2 Correct 21 ms 8540 KB Output is correct
3 Correct 55 ms 14252 KB Output is correct
4 Correct 51 ms 13404 KB Output is correct
5 Correct 128 ms 22868 KB Output is correct
6 Correct 133 ms 20816 KB Output is correct
7 Correct 124 ms 22940 KB Output is correct
8 Correct 145 ms 20896 KB Output is correct
9 Correct 112 ms 20304 KB Output is correct
10 Correct 113 ms 20208 KB Output is correct