Submission #289114

#	Time	Username	Problem	Language	Result	Execution time	Memory
289114		abyyskit	Ideal city (IOI12_city)	C++14	11 / 100	1091 ms	4160 KiB

city

#include<bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for(int i = x; i < y; ++i)
#define pb push_back
#define x first
#define y second

long long M;
long long ans;
set<pair<int, int>> g;
vector<pair<int ,int>> D;
map<pair<int, int>, int> ind;

void Add(int x){
	ans = (ans + (long long)x)%M;
}

void bfs(pair<int, int> start){
	set<pair<int, int>> vis;
	queue<pair<pair<int, int>, int>> q;
	q.push({start, 0});
	while(!q.empty()){
		auto cur = q.front();
		q.pop();
		if (vis.count(cur.x) == 0){
			vis.insert(cur.x);
			if (ind[cur.x] > ind[start]){
				Add(cur.y);
			}
			pair<int, int> nex;
			FOR(i, 0, 4){
				nex = make_pair(cur.x.x + D[i].x, cur.x.y + D[i].y);
				if (g.count(nex) != 0 && vis.count(nex) == 0){
					q.push({nex, cur.y + 1});
				}
			}
		}
	}
}

int DistanceSum(int N, int *X, int *Y) {
	M = 1e9;
	ans = 0;
	D = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
	FOR(i, 0, N){
		g.insert({X[i], Y[i]});
		ind[make_pair(X[i], Y[i])] = i;
	}
	for(auto i: g){
		bfs(i);
	}
	return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45