oj.uz

Submission #365184

# Submission time Handle Problem Language Result Execution time Memory
365184 2021-02-11T07:41:51 Z Seanliu Ideal city (IOI12_city) C++14
100 / 100
 303 ms 19304 KB 
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#define pii pair<int,int>
#define F first
#define S second
#define ll long long int
using namespace std;

const int MOD = 1e9, maxN = 1e5 + 326;
vector<pii> points;
map<pii, int> mp;
vector<int> adj[maxN];
set<pii> edges;

ll ans[maxN], up[maxN], sz[maxN], cnt[maxN];

ll add(ll a, ll b){
	return (a + b >= MOD ? a + b - MOD : a + b);
}

ll sub(ll a, ll b){
	return (a >= b ? a - b : a - b + MOD);
}

void dfs(int p = 1, int u = 1){
	ans[u] = up[u] = 0;
	sz[u] = cnt[u];
	for(int v : adj[u]) if(v != p){
		dfs(u, v);
		ans[u] = add(ans[u], up[u] * sz[v] % MOD);
		ans[u] = add(ans[u], add(up[v], sz[v]) * sub(sz[u], cnt[u]) % MOD);
		sz[u] = add(sz[u], sz[v]);
		up[u] = add(up[u], add(up[v], sz[v]));
		ans[u] = add(ans[u], ans[v]);
		//from the last
	}
	//cout << "before updating up: " << ans[u] << endl;
	ans[u] = add(ans[u], up[u] * cnt[u] % MOD);
	//cout << "for " << u << ": ans = " << ans[u] << ", up = " << up[u] << ", sz = " << sz[u] << endl;
}

inline int run(int N){
	sort(points.begin(), points.end());
	mp = map<pii, int>();
	edges = set<pii>();
	fill(cnt, cnt + N + 1, 0);
	int c = 1;
	for(int i = 0; i < N; i++){
		auto [x, y] = points[i];
		if(mp.count({x, y - 1})) mp[{x, y}] = mp[{x, y - 1}];
		else mp[{x, y}] = c++;
		cnt[mp[{x, y}]]++;
		//cout << "mp[" << x << ", " << y << "] = " << mp[{x, y}] << endl;
	}
	fill(adj, adj + c + 1, vector<int>());
	for(auto [x, y] : points){
		if(mp.count({x - 1, y}) && !edges.count({mp[{x - 1, y}], mp[{x, y}]})){
			edges.insert({mp[{x - 1, y}], mp[{x, y}]});
			edges.insert({mp[{x, y}], mp[{x - 1, y}]});
		}
	}
	for(auto [u, v] : edges) adj[u].push_back(v);	
	dfs();
	return ans[1];
}


int DistanceSum(int N, int *X, int *Y){
	for(int i = 0; i < N; i++) points.emplace_back(X[i], Y[i]);
	ll ans = run(N);
	//cout << "Vertical: " << ans << endl;
	for(auto &p : points) swap(p.F, p.S);
	ans = add(ans, run(N));
	return ans;
}

Compilation message

city.cpp: In function 'int run(int)':
city.cpp:53:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   53 |   auto [x, y] = points[i];
      |        ^
city.cpp:60:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |  for(auto [x, y] : points){
      |           ^
city.cpp:66:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |  for(auto [u, v] : edges) adj[u].push_back(v);
      |           ^

Subtask #1
11.0 / 11.0

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

Subtask #2
21.0 / 21.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 4712 KB Output is correct
2 Correct 42 ms 4712 KB Output is correct
3 Correct 112 ms 7532 KB Output is correct
4 Correct 112 ms 7660 KB Output is correct
5 Correct 237 ms 12264 KB Output is correct
6 Correct 239 ms 12392 KB Output is correct
7 Correct 239 ms 12776 KB Output is correct
8 Correct 233 ms 12112 KB Output is correct
9 Correct 245 ms 12776 KB Output is correct
10 Correct 258 ms 19304 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 5864 KB Output is correct
2 Correct 49 ms 5480 KB Output is correct
3 Correct 146 ms 10604 KB Output is correct
4 Correct 134 ms 9324 KB Output is correct
5 Correct 303 ms 18152 KB Output is correct
6 Correct 266 ms 14696 KB Output is correct
7 Correct 301 ms 18536 KB Output is correct
8 Correct 271 ms 14824 KB Output is correct
9 Correct 260 ms 14184 KB Output is correct
10 Correct 258 ms 13816 KB Output is correct