oj.uz

Submission #289114

# Submission time Handle Problem Language Result Execution time Memory
289114 2020-09-02T11:15:33 Z abyyskit Ideal city (IOI12_city) C++14
11 / 100
 1000 ms 4160 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Correct 28 ms 288 KB Output is correct
7 Correct 30 ms 384 KB Output is correct
8 Correct 26 ms 384 KB Output is correct
9 Correct 29 ms 384 KB Output is correct
10 Correct 31 ms 384 KB Output is correct
11 Correct 31 ms 384 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 940 ms 544 KB Output is correct
2 Correct 926 ms 512 KB Output is correct
3 Execution timed out 1089 ms 512 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1040 ms 3832 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 1091 ms 4160 KB Time limit exceeded
2 Halted 0 ms 0 KB -