Submission #1171400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171400		uranhishig	Circle Passing (EGOI24_circlepassing)	C++20	20 / 100	18 ms	5196 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define pb push_back
#define int long long
#define ff first
#define ss second
#define all(a) (a).begin(),(a).end()
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)

const int mx = 2e5 + 9;
vector<vector<int>> v(mx);
vector<bool> vis(mx);

queue<pair<int, int>> q1;
map<int, int> mp;


void bfs1(int s, int e){
	q1.push({s,0});
	vis[s]=1;
	while(!q1.empty()){
	    int x = q1.front().first;
	    int w = q1.front().second;
		q1.pop();
		if (x==e) {
//			cout<<w<<endl;
			mp[x] = w;
			return;
		}
		for (auto y:v[x]) {
			if (!vis[y]) {
				vis[y]=1;
				mp[y] = w + 1;
				q1.push({y,w+1});
			}
		}
	}
	mp[e] = 0;
}


void bfs(int s, int e,queue<pair<int, int>> &q ){
	q.push({s,0});
	vis[s]=1;
	while(!q.empty()){
	    int x = q.front().first;
	    int w = q.front().second;
		q.pop();
		if (x==e) {
			cout<<w<<endl;
			return;
		}
		for (auto y:v[x]) {
			if (!vis[y]) {
				vis[y]=1;
				q.push({y,w+1});
			}
		}
	}
	cout<<'0'<< endl;
}


signed main() {
	int n, m, t;	cin >> n >> m >> t;
	for (int i = 0; i < m; i++)	{
		int p;	cin >> p;
		v[p].pb(n + p);
		v[n + p].pb(p);
	}
	v[2 * n - 1].pb(0);
	v[0].pb(2 * n - 1);
	for (int i = 0; i < 2 * n - 1; i++) {
	    v[i].pb(i + 1);
	    v[i + 1].pb(i);
	}
	if (n <= 1000 and t <= 1000 and m <= 1000) {
		for (int i = 0; i < n; i++) {	vis[i] = false;	}
		while (t--) {
		    fill(vis.begin(), vis.end(), false);
		    queue<pair<int , int>>q;
		    int x, y;   cin >> x >> y;
		    bfs(x, y, q);
		}
	}
	bfs1(0, 2 * n - 1);
	for (int i = 0; i < t; i++) {
		int x;	cin >> x;
		cout << mp[x] << endl;
	}
	return 0; 
}

• Subtask 1: 0 / 14
• Subtask 2: 20 / 20
• Subtask 3: 0 / 22
• Subtask 4: 0 / 17
• Subtask 5: 0 / 27