oj.uz

Submission #439922

# Submission time Handle Problem Language Result Execution time Memory
439922 2021-07-01T08:20:07 Z AmShZ Ideal city (IOI12_city) C++11
32 / 100
 1000 ms 92904 KB 
//khodaya khodet komak kon
# include <bits/stdc++.h>

using namespace std;

typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <pii, int>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
typedef pair <ll, ll>                                    pll;

# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define lc                                              id << 1
# define rc                                              id << 1 | 1
# define InTheNameOfGod                                  ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);

ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}

const int xn = 1e5 + 10;
const int xm = - 20 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const ld eps = 1e-15;
const int mod = 1e9;// + 7;//998244353;
const int base = 257;

int n, dist[xn], sz[xn], par[xn];
pii a[xn];
ll ans;
map <pii, int> mp;
vector <int> adj[xn], G[xn];
vector <pii> E;
queue <int> q;

void add_edge(int v, int u){
	adj[v].push_back(u);
	adj[u].push_back(v);
	E.push_back({v, u});
}
void DFS(int v){
	sz[v] = 1;
	for (int u : G[v]){
		DFS(u);
		ans += 1ll * sz[u] * (n - sz[u]);
		sz[v] += sz[u];
	}
}
ll DistanceSum(int N, int *X, int *Y){
	n = N;
	ans = 0;
	mp.clear(), E.clear();
	for (int i = 1; i <= n; ++ i)
		adj[i].clear(), dist[i] = - 1;
	for (int i = 1; i <= n; ++ i)
		a[i] = {X[i - 1], Y[i - 1]}, mp[a[i]] = i;
	for (int i = 1; i <= n; ++ i){
		int x = a[i].A, y = a[i].B;
		if (mp[{x - 1, y}])
			add_edge(i, mp[{x - 1, y}]);
		if (mp[{x, y - 1}])
			add_edge(i, mp[{x, y - 1}]);
	}
	for (int i = 1; i <= n; ++ i){
		for (int j = 1; j <= n; ++ j)
			dist[j] = - 1;
		dist[i] = 0;
		q.push(i);
		while (SZ(q)){
			int v = q.front();
			q.pop();
			ans += dist[v];
			for (int u : adj[v]){
				if (dist[u] == - 1){
					q.push(u);
					dist[u] = dist[v] + 1;
					G[v].push_back(u);
					par[u] = v;
				}
			}
		}
	}
	return ans / 2;
	DFS(1);
	for (pii e : E){
		int v = e.A, u = e.B;
		if (v == par[u] || u == par[v])
			continue;
		ans -= 2ll * sz[v] * sz[u];
	}
	return ans % mod;
}

/*
int main(){
	//InTheNameOfGod;

	int X[11] = {2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5};
	int Y[11] = {5, 6, 3, 6, 3, 4, 5, 6, 3, 4, 6};
	//int X[4] = {1, 1, 2, 2};
	//int Y[4] = {1, 2, 1, 2};
	cout << DistanceSum(11, X, Y) << endl;

	return 0;
}
*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 6 ms 5196 KB Output is correct
7 Correct 6 ms 5196 KB Output is correct
8 Correct 5 ms 5264 KB Output is correct
9 Correct 5 ms 5196 KB Output is correct
10 Correct 5 ms 5196 KB Output is correct
11 Correct 5 ms 5260 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 9952 KB Output is correct
2 Correct 55 ms 10456 KB Output is correct
3 Correct 110 ms 18448 KB Output is correct
4 Correct 109 ms 18552 KB Output is correct
5 Correct 198 ms 23856 KB Output is correct
6 Correct 212 ms 25272 KB Output is correct
7 Correct 202 ms 23932 KB Output is correct
8 Correct 212 ms 25028 KB Output is correct
9 Correct 235 ms 26156 KB Output is correct
10 Correct 212 ms 26308 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 92904 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1075 ms 91712 KB Time limit exceeded
2 Halted 0 ms 0 KB -