oj.uz

Submission #73617

# Submission time Handle Problem Language Result Execution time Memory
73617 2018-08-28T15:26:50 Z FLDutchman Ideal city (IOI12_city) C++14
55 / 100
 1000 ms 36880 KB 
#include <bits/stdc++.h>
using namespace std;

typedef int INT;

#define pb push_back
#define int long long
#define fst first
#define snd second
#define FOR(i,l,r) for(int i = (l); i < (r); i++)

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef vector<ii> vii;

int N;
vii points;
vvi adj;
map<ii, int> idx;
vvi rowgr, colgr;
vi rowsz, colsz;
vi row, col;
vi vis;

void flood(int u, int c, bool co){
	vis[u] = 1;
	if(co) col[u] = c, colsz[c] ++;
	else row[u] = c, rowsz[c] ++;
	for(int i = co; i < 4; i+= 2) if(adj[u][i] != -1 and !vis[adj[u][i]]) flood(adj[u][i], c, co);
	for(int i = 1-co; i < 4; i+= 2) if(adj[u][i] != -1 and vis[adj[u][i]]) {
		int v = adj[u][i];
		if(v == -1) continue;
		if(co) colgr[c].pb(col[v]), colgr[col[v]].pb(c);
		else rowgr[c].pb(row[v]), rowgr[row[v]].pb(c);
	}
}


map<ii, int> dp[2];
int dfs(int u, int p, bool col){
	int &res = dp[col][{u, p}];	
	if(res != 0) return res;
	res = col ? colsz[u] : rowsz[u];
	for(int v : (col ? colgr[u] : rowgr[u]) ) if(v != p) res += dfs(v, u, col);
	return res;
}


int gettot(int u, int tot){
	//cout << u << " " << tot << endl;
	int res = tot;
	vis[u] = 1;
	FOR(i, 0, 4){
		int v = adj[u][i];
		if(v == -1 || vis[v]) continue;
		if(i % 2 == 0) { res += gettot(v, tot - dfs(col[v], col[u], 1) + dfs(col[u], col[v], 1));  }
		else res += gettot(v, tot - dfs(row[v], row[u], 0) + dfs(row[u], row[v], 0));
	}
	return res;
}

int bfs(int u){
	vis.assign(N, 0);
	int total = 0;
	queue<ii> q;
	q.push({u, 0});
	vis[u] = 1;
	while(!q.empty()){
		ii p = q.front(); q.pop();
		total += p.snd;

		for(int v : adj[p.fst])if(v !=-1 and !vis[v]){
			q.push({v,p.snd+1});
			vis[v] = 1;
		}
	}
	vis.assign(N, 0);
	return total;
}

INT DistanceSum(INT n, INT *X, INT *Y) {
	N = n;
	adj.assign(N, vi(4, -1));
	FOR(i, 0, N) {points.pb({X[i], Y[i]}); idx[{X[i], Y[i]}] = i+1;}
	FOR(i, 0, N){
		int x = X[i], y = Y[i];
		int neigh;
		if(neigh = idx[{x+1, y}]) adj[i][0] = neigh-1;
		if(neigh = idx[{x, y-1}]) adj[i][1] = neigh-1;
		if(neigh = idx[{x-1, y}]) adj[i][2] = neigh-1;
		if(neigh = idx[{x, y+1}]) adj[i][3] = neigh-1;
	}
	idx.clear();
	int k = 0;
	row.assign(N, -1);
	col.assign(N, -1);
	
	vis.assign(N, 0);
	FOR(i, 0, N) if(!vis[i]){
		rowgr.pb(vi(0));
		rowsz.pb(0);
		flood(i, k++,0);
	}
	for(auto &v : rowgr){
		sort(v.begin(), v.end());
		v.erase(unique(v.begin(), v.end()), v.end());
	}
	k = 0;


	vis.assign(N, 0);
	FOR(i, 0, N) if(!vis[i]){
		colgr.pb(vi(0));
		colsz.pb(0);
		flood(i, k++,1);
	}

	vis.assign(N, 0);




	for(auto &v : colgr){
		sort(v.begin(), v.end());
		v.erase(unique(v.begin(), v.end()), v.end());
	}

/*
	for(auto &v : adj) {
		for(int k : v) cout << k << " ";
		cout<<endl;
	}

	for(auto &v : colgr) {
		for(int k : v) cout << k << " ";
		cout<<endl;
	}
	cout<<endl;
	for(auto &v : rowgr) {
		for(int k : v) cout << k << " ";
		cout<<endl;
	}

	for(int k : col) cout << k << " ";
	cout<<endl;
	for(int k : row) cout << k << " ";
	cout<<endl;
	cout << dfs(1, 0, 0) << endl;
	cout << bfs(0) <<endl;
*/
  	return (gettot(0, bfs(0))/2) % 1000000000;
}

Compilation message

city.cpp: In function 'INT DistanceSum(INT, INT*, INT*)':
city.cpp:89:12: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   if(neigh = idx[{x+1, y}]) adj[i][0] = neigh-1;
city.cpp:90:12: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   if(neigh = idx[{x, y-1}]) adj[i][1] = neigh-1;
city.cpp:91:12: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   if(neigh = idx[{x-1, y}]) adj[i][2] = neigh-1;
city.cpp:92:12: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   if(neigh = idx[{x, y+1}]) adj[i][3] = neigh-1;

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 600 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 4 ms 680 KB Output is correct
7 Correct 3 ms 684 KB Output is correct
8 Correct 3 ms 688 KB Output is correct
9 Correct 4 ms 748 KB Output is correct
10 Correct 4 ms 752 KB Output is correct
11 Correct 4 ms 756 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1016 KB Output is correct
2 Correct 5 ms 1028 KB Output is correct
3 Correct 7 ms 1176 KB Output is correct
4 Correct 7 ms 1204 KB Output is correct
5 Correct 8 ms 1344 KB Output is correct
6 Correct 7 ms 1344 KB Output is correct
7 Correct 9 ms 1388 KB Output is correct
8 Correct 7 ms 1404 KB Output is correct
9 Correct 8 ms 1404 KB Output is correct
10 Correct 8 ms 1404 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 6056 KB Output is correct
2 Correct 65 ms 6156 KB Output is correct
3 Correct 213 ms 13756 KB Output is correct
4 Correct 236 ms 13884 KB Output is correct
5 Correct 510 ms 27408 KB Output is correct
6 Correct 551 ms 27752 KB Output is correct
7 Correct 496 ms 28500 KB Output is correct
8 Correct 536 ms 29904 KB Output is correct
9 Correct 573 ms 29904 KB Output is correct
10 Correct 779 ms 33688 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 33688 KB Output is correct
2 Correct 101 ms 33688 KB Output is correct
3 Correct 447 ms 33688 KB Output is correct
4 Correct 469 ms 33688 KB Output is correct
5 Execution timed out 1076 ms 36880 KB Time limit exceeded
6 Halted 0 ms 0 KB -