Submission #237333

#	Time	Username	Problem	Language	Result	Execution time	Memory
237333		wwdd	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	87 ms	93352 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
const int SQ = 1500;
const int MN = 30030;
struct chash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
	size_t operator()(ii x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(splitmix64(x.first+FIXED_RANDOM)+x.second+FIXED_RANDOM);
	}
};

unordered_map<ii,int, chash> dist;
ii ok[MN];
vi go[MN];
bitset<MN> vs;
int dx[2] = {-1,1};
short had[MN][SQ];
int ged(int u, int p) {
	if(p < SQ) {return had[u][p];}
	if(dist.count({u,p})) {
		return dist[{u,p}];
	}
	return -1;
}
void sed(int u, int p, int val) {
	if(p < SQ) {
		had[u][p] = val;
		return;}
	dist[{u,p}] = val;
}
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int n,m;
	cin >> n >> m;
	memset(had,-1,sizeof(had));
	for(int i=0;i<m;i++) {
		int a,p;
		cin >> a >> p;
		ok[i] = {a,p};
		go[a].push_back(p);
	}
	deque<ii> q;
	int sr = ok[0].first;
	vs.set(sr);
	for(int i=0;i<go[sr].size();i++) {
		if(ged(sr,go[sr][i]) == -1) {
			q.push_front({sr,go[sr][i]});
			sed(sr,go[sr][i],0);
		}
	}
	int res = -1;
	int fin = ok[1].first;
	while(!q.empty()) {
		ii co = q.front();q.pop_front();
		int u = co.first;
		int p = co.second;
		int di = ged(u,p);
		//cout << "look " << u << " " << p << " = " << di << '\n';
		if(u == fin) {
			res = di;break;
		}
		if(!vs[u]) {
			vs.set(u);
			//cout << "unlock " << u << '\n';
			for(int i=0;i<go[u].size();i++) {
				if(ged(u,go[u][i]) == -1) {
					q.push_front({u,go[u][i]});
					sed(u,go[u][i],di);
				}
			}
			q.push_front(co);
			continue;
		}
		for(int i=0;i<2;i++) {
			int v = u+dx[i]*p;
			if(v < 0 || v >= n) {continue;}
			if(ged(v,p) != -1) {continue;}
			sed(v,p,di+1);
			q.push_back({v,p});
		}
	}
	cout << res << '\n';
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:60:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<go[sr].size();i++) {
              ~^~~~~~~~~~~~~~
skyscraper.cpp:80:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<go[u].size();i++) {
                ~^~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 0 / 43