oj.uz

Submission #519107

# Submission time Handle Problem Language Result Execution time Memory
519107 2022-01-25T16:36:33 Z AdamGS Ideal city (IOI12_city) C++17
100 / 100
 70 ms 9540 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7;
const ll MOD=1e9;
vector<int>V[LIM];
pair<int,int>T[LIM];
map<int,int>mp;
ll F[LIM], ile[LIM], n, ans;
int fnd(int x) {
	if(F[x]==x) return x;
	return F[x]=fnd(F[x]);
}
void uni(int a, int b) {
	if(fnd(a)==fnd(b)) return;
	ile[fnd(a)]+=ile[fnd(b)];
	F[fnd(b)]=fnd(a);
}
ll DFS(int x, int o) {
	ll s=ile[x];
	for(auto i : V[x]) if(i!=o) s+=DFS(i, x);
	ans+=s*(n-s);
	ans%=MOD;
	return s;
}
int DistanceSum(int N, int *X, int *Y) {
	n=N;
	rep(i, n) T[i]={X[i], Y[i]};
	rep(j, 2) {
		mp.clear();
		rep(i, n) {
			swap(T[i].st, T[i].nd);
			F[i]=i;
			ile[i]=1;
			V[i].clear();
		}
		sort(T, T+n);
		rep(i, n-1) {
			if(T[i].st==T[i+1].st && T[i].nd+1==T[i+1].nd) uni(i, i+1);
		}
		rep(i, n) {
			int x=mp[T[i].nd]-1;
			if(x>=0 && T[x].st==T[i].st-1 && (!V[fnd(i)].size() || V[fnd(i)].back()!=fnd(x))) {
				V[fnd(i)].pb(fnd(x));
				V[fnd(x)].pb(fnd(i));
			}
			mp[T[i].nd]=i+1;
		}
		DFS(fnd(0), fnd(0));
	}
	return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 2 ms 2556 KB Output is correct
8 Correct 2 ms 2636 KB Output is correct
9 Correct 2 ms 2636 KB Output is correct
10 Correct 2 ms 2636 KB Output is correct
11 Correct 2 ms 2664 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2656 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2664 KB Output is correct
4 Correct 3 ms 2636 KB Output is correct
5 Correct 4 ms 2764 KB Output is correct
6 Correct 3 ms 2764 KB Output is correct
7 Correct 3 ms 2796 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 2 ms 2764 KB Output is correct
10 Correct 3 ms 2764 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3404 KB Output is correct
2 Correct 10 ms 3440 KB Output is correct
3 Correct 25 ms 4728 KB Output is correct
4 Correct 22 ms 4676 KB Output is correct
5 Correct 53 ms 6612 KB Output is correct
6 Correct 45 ms 6620 KB Output is correct
7 Correct 49 ms 6912 KB Output is correct
8 Correct 50 ms 6572 KB Output is correct
9 Correct 45 ms 6884 KB Output is correct
10 Correct 53 ms 9540 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3928 KB Output is correct
2 Correct 14 ms 3780 KB Output is correct
3 Correct 33 ms 5684 KB Output is correct
4 Correct 31 ms 5336 KB Output is correct
5 Correct 67 ms 8660 KB Output is correct
6 Correct 60 ms 7656 KB Output is correct
7 Correct 70 ms 8784 KB Output is correct
8 Correct 57 ms 7644 KB Output is correct
9 Correct 55 ms 7364 KB Output is correct
10 Correct 55 ms 7280 KB Output is correct