Submission #1170888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170888		uranhishig	Circle Passing (EGOI24_circlepassing)	C++20	20 / 100	2095 ms	11412 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#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);

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 < n; i++) {
	    vis[i] = false;
	}
	for (int i = 0; i < m; i++)	{
		int p;	cin >> p;
		v[p].push_back(n + p);
		v[n + p].push_back(p);
	}
	v[2 * n - 1].push_back(0);
	v[0].push_back(2 * n - 1);
	for (int i = 0; i < 2 * n - 1; i++) {
	    v[i].push_back(i + 1);
	    v[i + 1].push_back(i);
	}
	while (t--) {
	    fill(vis.begin(), vis.end(), false);
	    queue<pair<int , int>>q;
	    int x, y;   cin >> x >> y;
	   // cout << " * ";
	    bfs(x, y, q);
	}
	return 0; 
}

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