Submission #289125

#	Time	Username	Problem	Language	Result	Execution time	Memory
289125		abyyskit	Ideal city (IOI12_city)	C++14	32 / 100	1094 ms	4088 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
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 (stderr)

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 / 11
• Subtask 2: 21 / 21
• Subtask 3: 0 / 23
• Subtask 4: 0 / 45