Submission #439922

#	Time	Username	Problem	Language	Result	Execution time	Memory
439922		AmShZ	Ideal city (IOI12_city)	C++11	32 / 100	1095 ms	92904 KiB

city

//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 / 11
• Subtask 2: 21 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45