Submission #528110

#	Time	Username	Problem	Language	Result	Execution time	Memory
528110		koioi.org-koosaga	From Hacks to Snitches (BOI21_watchmen)	C++17	70 / 100	6072 ms	331756 KiB

watchmen

#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
typedef long long lint;
typedef pair<lint, lint> pi;
const int mod = 1e9 + 7;
const int MAXN = 250005;
const int MAXL = 2755;

vector<lint> dist[MAXN];
vector<int> gph[MAXN];
vector<int> ngph[MAXL];
lint eist[MAXL][MAXL];

struct node{
	int x, y; lint dist;
	bool mode;
	bool operator<(const node &n)const{
		return dist > n.dist;
	}
};

void solve(int n, vector<pi> edg, vector<int> vect, int s, int e){
	memset(eist, 0x3f, sizeof(eist));
	vector<int> sum = {0};
	for(auto &i : vect){
		int nxt = i + sum.back(); sum.push_back(nxt);
	}
	int p = 0;
	vector<pi> cycs;
	for(int i = 0; i < sz(vect); i++){
		for(int j = 0; j < vect[i]; j++){
			dist[p].resize(vect[i], 1e18);
			p++;
			cycs.emplace_back(i, j);
		}
	}
	while(p < n){
		dist[p++].resize(1, 1e18);
		cycs.emplace_back(-1, 0);
	}
	for(auto &[u, v] : edg){
		if(cycs[u].first >= 0 && cycs[v].first >= 0){
			ngph[u].push_back(v);
			ngph[v].push_back(u);
		}
		else{
			gph[u].push_back(v);
			gph[v].push_back(u);
		}
	}
	for(int i = 0; i < n; i++){
		sort(all(gph[i]));
		sort(all(ngph[i]));
	}
	priority_queue<node> pq;
	auto enq = [&](int v, lint d){
		if(sz(dist[v]) > 1 && d % sz(dist[v]) == cycs[v].second) return;
		if(dist[v][d % sz(dist[v])] > d){
			dist[v][d % sz(dist[v])] = d;
			pq.push({v, (int)(d % sz(dist[v])), d, 0});
		}
	};
	auto enq2 = [&](int x, int y, lint d){
		if(eist[x][y] > d){
			eist[x][y] = d;
			pq.push({x, y, d, 1});
		}
	};
	memset(eist, 0x3f, sizeof(eist));
	enq(s, 0);
	vector<int> visCount(n);
	while(sz(pq)){
		auto x = pq.top(); pq.pop();
		int v = x.x;
		int w = x.y;
		if(x.mode == 0){
			if(dist[v][w] != x.dist) continue;
			enq(v, x.dist + 1);
			visCount[v]++;
			for(auto &y : gph[v]){
				if(sz(dist[v]) > 1 && visCount[v] > 1 && sz(dist[y]) == 1) break;
				enq(y, x.dist + 1);
				if(sz(dist[v]) == 1 && sz(dist[y]) > 1){
					enq(y, x.dist + 1 + ((cycs[y].second - x.dist) % sz(dist[y]) + sz(dist[y])) % sz(dist[y]));
				}
			}
			if(sz(dist[v]) > 1){
				for(int i = 0; i < sz(vect); i++){
					lint newDist = x.dist;
					enq2(v, sum[i] + newDist % vect[i], newDist);
				}
			}
		}
		else{
			if(eist[v][w] != x.dist) continue;
			int pos = cycs[w].first;
			enq2(v, sum[pos] + (x.dist + sz(dist[v])) % vect[pos], x.dist + sz(dist[v]));
			int s = lower_bound(all(ngph[v]), w - cycs[w].second) - ngph[v].begin();
			for(int i = s; i < sz(ngph[v]); i++){
				int y = ngph[v][i];
				if(cycs[y].first != cycs[w].first) break;
				if(cycs[v].first >= 0 &&
						cycs[v].first == cycs[y].first &&
						x.dist % sz(dist[v]) == cycs[y].second &&
						(x.dist + 1) % sz(dist[v]) == cycs[v].second){
					continue;
				}
				enq(y, x.dist + 1);
			}
		}
	}
	lint ans = *min_element(all(dist[e]));
	if(ans < 1e17) cout << ans << "\n";
	else cout << "impossible\n";
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m; cin >> n >> m;
	vector<pi> edg;
	for(int i = 0; i < m; i++){
		int u, v; cin >> u >> v;
		edg.emplace_back(u-1, v-1);
	}
	vector<int> idx(n, -1);
	int cnt = 0;
	int k; cin >> k;
	vector<int> siz(k);
	for(int i = 0; i < k; i++){
		cin >> siz[i];
		for(int j = 0; j < siz[i]; j++){
			int v; cin >> v;
			idx[v - 1] = cnt++;
		}
	}
	for(int i = 0; i < n; i++){
		if(idx[i] == -1) idx[i] = cnt++;
	}
	for(auto &[u, v] : edg){
		u = idx[u];
		v = idx[v];
	}
	solve(n, edg, siz, idx[0], idx[n - 1]);
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 25 / 25
• Subtask 6: 20 / 20
• Subtask 7: 0 / 20