QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #672166 | #6772. Spicy Restaurant | ACAAA# | TL | 1ms | 5644kb | C++23 | 1.2kb | 2024-10-24 15:54:40 | 2024-10-24 15:55:24 |
Judging History
answer
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 5e5 + 10,M=1e5+10;
typedef pair<int, int>pii;
int n, m, k, w[M],ans[N],minn=1000;
vector<int>a[M];
pii p[N];
struct State {
int who,pos,dis;
};
void bfs() {
for (int i = 1; i <= k; i++)
ans[i] = 1e9;
queue<State>q;
for (int i = 1; i <= k; i++) {
if (minn > p[i].second)
ans[i] = -1;
else
q.push({ i,p[i].first,0 });
}
while (!q.empty()) {
State s = q.front();
q.pop();
if (ans[s.who] != 1e9)
continue;
if (p[s.who].second >= w[s.pos])
ans[s.who] = s.dis;
for (int i = 0; i < a[s.pos].size(); i++) {
int v = a[s.pos][i];
q.push({ s.who,v,s.dis + 1 });
}
}
}
int main() {
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
cin >> w[i];
minn = min(minn, w[i]);
}
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
a[u].push_back(v);
a[v].push_back(u);
}
for (int i = 1; i <= k; i++) {
int pos, w;
cin >> pos >> w;
p[i] = { pos,w };
}
bfs();
for (int i = 1; i <= k; i++) {
cout << ans[i] << "\n";
}
}
/*
4 4 5
5 4 2 3
1 2
2 3
3 4
4 1
1 1
1 2
1 3
1 4
1 5
- 1
2
1
1
0
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5644kb
input:
4 4 5 5 4 2 3 1 2 2 3 3 4 4 1 1 1 1 2 1 3 1 4 1 5
output:
-1 2 1 1 0
result:
ok 5 lines
Test #2:
score: -100
Time Limit Exceeded
input:
50000 100000 100000 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 ...