oj.uz

답안 #1024394

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1024394 2024-07-16T03:47:18 Z socpite 이상적인 도시 (IOI12_city) C++17
100 / 100
 133 ms 23136 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])%mod;
	re %= mod;
	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, set<int>> mp;
	map<pair<int, int>, int> id;
	for(int i = 0; i < N; i++)mp[X[i]].insert(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
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 5724 KB Output is correct
2 Correct 21 ms 6236 KB Output is correct
3 Correct 54 ms 10064 KB Output is correct
4 Correct 54 ms 10660 KB Output is correct
5 Correct 111 ms 17140 KB Output is correct
6 Correct 116 ms 18216 KB Output is correct
7 Correct 115 ms 17940 KB Output is correct
8 Correct 113 ms 17068 KB Output is correct
9 Correct 116 ms 18004 KB Output is correct
10 Correct 124 ms 23136 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 5980 KB Output is correct
2 Correct 26 ms 6192 KB Output is correct
3 Correct 61 ms 10320 KB Output is correct
4 Correct 59 ms 10556 KB Output is correct
5 Correct 130 ms 17696 KB Output is correct
6 Correct 133 ms 18004 KB Output is correct
7 Correct 124 ms 17748 KB Output is correct
8 Correct 127 ms 17656 KB Output is correct
9 Correct 119 ms 17376 KB Output is correct
10 Correct 119 ms 17492 KB Output is correct