oj.uz

Submission #1024390

# Submission time Handle Problem Language Result Execution time Memory
1024390 2024-07-16T03:41:58 Z socpite Ideal city (IOI12_city) C++17
0 / 100
 181 ms 262144 KB 
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5+5;

const int mod = 1e9;

vector<int> g[maxn];
int W[maxn];

long long dfs(int x, int p, int N){
	long long re = 0;
	for(auto v: g[x]){
		if(v == p)continue;
		re += dfs(v, x, N);
		W[x] += W[v];
	}
	re += 1LL*W[x]*(N - W[x]);
	return re;
}

long long solve(int N, int *X, int *Y){
	for(int i = 1; i <= N; i++){
		g[i].clear();
		W[i] = 0;
	}
	int cnt = 0;
	map<int, vector<int>> mp;
	map<pair<int, int>, int> id;
	for(int i = 0; i < N; i++)mp[X[i]].push_back(Y[i]);
	for(auto v: mp){
		int prv = -2;
		for(auto pos: v.second){
			if(pos == prv + 1)id[{v.first, pos}] = cnt;
			else id[{v.first, pos}] = ++cnt;
			W[cnt]++;
			if(id.find({v.first-1, pos}) != id.end()){
				int prvid = id[{v.first-1, pos}];
				g[cnt].push_back(prvid);
				g[prvid].push_back(cnt);
			}
			prv = pos;
		}
	}
	for(int i = 1; i <= cnt; i++){
		sort(g[i].begin(), g[i].end());
		g[i].erase(unique(g[i].begin(), g[i].end()), g[i].end());
	}
	return dfs(1, 0, N);
}


int DistanceSum(int N, int *X, int *Y) {
	long long ans = solve(N, X, Y);
	for(int i = 0; i < N; i++)swap(X[i], Y[i]);
	ans += solve(N, X, Y);
	return ans%mod;

}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 Runtime error 181 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 161 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -