QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#779145 | #6772. Spicy Restaurant | zzz666 | WA | 42ms | 8892kb | C++17 | 3.1kb | 2024-11-24 17:38:10 | 2024-11-24 17:38:14 |
Judging History
answer
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define ll long long
#define llu unsigned long long
#define endl "\n"
#define rp(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define fp(i,a,b) for(int i=a;i>=b;i--)
#define IOS ios::sync_with_stdio(false),cout.tie(0),cin.tie(0);
const int INF = 1e9+10;
const ll mod = 998244353;
const int N = 1e5+6;
using namespace std;
typedef pair<int, int> PII;
inline __int128 read(){
__int128 x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
inline void write(__int128 x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9) write(x/10);
putchar(x%10+'0');
}
ll ksm(ll a, ll b)
{
ll res = 1;
while(b > 0)
{
if (b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
void exgcd(int a, int b, int& x, int& y){
if(b == 0){
x=1,y=0;
return;
}
exgcd(b,a%b,y,x);
y-=a/b*x;
}
void c_prime(int n) {
vector<ll> pri;
bool not_prime[500005];//用的时候两个数组都开全局//不是质数的标记
for (int i = 2; i <= n; ++i){
if(!not_prime[i]){
pri.push_back(i);
}
for (int pri_j : pri) {
if (i * pri_j > n) break;
not_prime[i * pri_j] = true;
if (i % pri_j == 0) {
break;
}
}
}
}
ll n,m,qq;
ll la[N];
vector<int>v[N];
ll ans;
queue<ll>q;
void bfs(ll p,ll lim,ll k)
{
//bool flag=true;
if(k>=n)
return ;
int cnt=v[p].size();
rp(i,0,cnt-1)
{
q.push(v[p][i]);
}
//q.pop();
while(cnt--)
{
if(la[q.front()]<=lim)
{
ans=min(ans,k);
while(!q.empty())
{
q.pop();
}
return ;
}
else
{
int t=q.front();
rp(i,0,(int)v[t].size()-1)
{
q.push(v[t][i]);
}
q.pop();
}
}
if(!q.empty())
bfs(q.front(),lim,k+1);
}
void solve() {
cin>>n>>m>>qq;
rp(i,1,n)
{
cin>>la[i];
}
//cout<<-1<<endl;
rp(i,1,m)
{
ll x,y;
cin>>x>>y;
//cout<<x<<y;
v[x].push_back(y);
v[y].push_back(x);
}
//cout<<-1<<endl;
while(qq--)
{
ll pp,x;
//cout<<-1<<endl;
cin>>pp>>x;
//cout<<-1<<endl;
ans=INF;
//cout<<-1<<endl;
if(la[pp]<=x)
{
cout<<0<<endl;
return ;
}
bfs(pp,x,1);
if(ans!=INF)
cout<<ans<<endl;
else
cout<<-1<<endl;
while(!q.empty())
{
q.pop();
}
}
//cout<<-1<<endl;
}
signed main()
{
//IOS
int TT = 1;
//cin>>TT;
while (TT--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 6316kb
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
Wrong Answer
time: 42ms
memory: 8892kb
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 ...
output:
0
result:
wrong answer 2nd lines differ - expected: '8', found: ''