oj.uz

Submission #289125

# Submission time Handle Problem Language Result Execution time Memory
289125 2020-09-02T11:36:49 Z abyyskit Ideal city (IOI12_city) C++14
32 / 100
 1000 ms 4088 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
struct node{
	vector<int> e;
	bool vis = false;
	
};
vector<node> G;
void reset(){
	FOR(i, 0, G.size()){
		G[i].vis = false;
	}
}
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(int start){
	queue<pair<int,int>> q;
	q.push({start, 0});
	while(!q.empty()){
		pair<int,int> cur = q.front();
		q.pop();
		if (!G[cur.x].vis){
			G[cur.x].vis = true;
			if (cur.x > start){
				Add(cur.y);
			}
			FOR(i, 0, G[cur.x].e.size()){
				int nex = G[cur.x].e[i];
				if (!G[nex].vis){
					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}};
	G.resize(N);
	FOR(i, 0, N){
		g.insert({X[i], Y[i]});
		ind[make_pair(X[i], Y[i])] = i;
	}
	FOR(i, 0, N){
		pair<int, int> nex;
		FOR(j, 0, 4){
			nex = {X[i] + D[j].x, Y[i] + D[j].y};
			if (g.count(nex)){
				G[i].e.pb(ind[nex]);
			}
		}
	}
	FOR(i, 0, N){
		reset();
		bfs(i);
	}
	return ans;
}

Compilation message

city.cpp: In function 'void reset()':
city.cpp:3:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
   14 |  FOR(i, 0, G.size()){
      |      ~~~~~~~~~~~~~~                    
city.cpp:14:2: note: in expansion of macro 'FOR'
   14 |  FOR(i, 0, G.size()){
      |  ^~~
city.cpp: In function 'void bfs(int)':
city.cpp:3:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
   39 |    FOR(i, 0, G[cur.x].e.size()){
      |        ~~~~~~~~~~~~~~~~~~~~~~~         
city.cpp:39:4: note: in expansion of macro 'FOR'
   39 |    FOR(i, 0, G[cur.x].e.size()){
      |    ^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 512 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 512 KB Output is correct
2 Correct 43 ms 512 KB Output is correct
3 Correct 86 ms 760 KB Output is correct
4 Correct 99 ms 760 KB Output is correct
5 Correct 158 ms 748 KB Output is correct
6 Correct 169 ms 760 KB Output is correct
7 Correct 153 ms 760 KB Output is correct
8 Correct 168 ms 760 KB Output is correct
9 Correct 166 ms 760 KB Output is correct
10 Correct 163 ms 640 KB Output is correct

Subtask #3
0 / 23.0

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