QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#691217 | #9431. The Quest for El Dorado | Evan | RE | 0ms | 3772kb | C++20 | 3.0kb | 2024-10-31 10:26:58 | 2024-10-31 10:27:01 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define tp tuple<int,int,int>
struct ST {
const int n, k;
vector<vector<int>> Max;
ST(int n) : n(n), k(__lg(n)) {
Max.resize(k + 1, vector<int>(n + 1));
}
void init() {
for (int i = 0, t = 1; i < k; i++, t <<= 1) {
const int T = n - (t << 1) + 1;
for (int j = 1; j <= T; j++) {
Max[i + 1][j] = max(Max[i][j], Max[i][j + t]);
}
}
}
int getMax(int l, int r) {
//printf("@%d %d\n",l,r);
if (l > r) {
swap(l, r);
}
int k = __lg(r - l + 1);
//printf("*%d\n", Max[0][0]);
return max(Max[k][l], Max[k][r - (1 << k) + 1]);
}
};
void solve()
{
int n,m,k;
int i,j,u,v,c,l,r;
scanf("%d %d %d",&n,&m,&k);
vector<tp> s[n+10];
for(i=1;i<=m;i++)
{
scanf("%d %d %d %d",&u,&v,&c,&l);
s[u].push_back({v,c,l});
s[v].push_back({u,c,l});
}
vector<pair<int,int>> t(k+10);
vector<pair<int,int>> st[m+10];
vector<int> vis(n+10);
for(i=1;i<=k;i++)
{
scanf("%d %d",&u,&v);
t[i]={u,v};
st[u].push_back({v,i});
}
vector<ST*> St(m + 10, nullptr);
for(i=1;i<=m;i++)
{
if(st[i].size())
{
St[i]=new ST(st[i].size());
for(j=0;j<st[i].size();j++)
{
St[i]->Max[0][j+1]=st[i][j].first;
}
St[i]->init();
}
}
priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<tuple<int,int,int>>> pq;
pq.push({1,0,1});
while(!pq.empty())
{
tp o=pq.top();pq.pop();
int x=get<0>(o),y=get<1>(o),z=get<2>(o);
if(vis[z]){continue;}
vis[z]=1;
for(i=0;i<s[z].size();i++)
{
if(vis[get<0>(s[z][i])]){continue;}
int xx=get<0>(s[z][i]),yy=get<1>(s[z][i]),zz=get<2>(s[z][i]);
if(t[x].first==yy&&y+zz<=t[x].second)
{
pq.push({x,y+zz,xx});
continue;
}
else
{
if(st[yy][st[yy].size()-1].second<=x){continue;}
l=0;r=st[yy].size()-1;
while(l<r)
{
int mid=(l+r)/2;
if(st[yy][mid].second<x+1){l=mid+1;}
else{r=mid-1;}
}
//printf("!%d %d\n",l,r);
r=st[yy].size()-1;
if(St[yy]->getMax(l+1,r+1)<zz){continue;}
while(l!=r)
{
int mid=(l+r)/2;
if(St[yy]->getMax(l+1,mid+1)>=zz){r=mid;}
else{l=mid+1;}
}
pq.push({st[yy][l].second,zz,xx});
}
}
}
for(i=1;i<=n;i++){printf("%d",vis[i]);}
printf("\n");
}
int main()
{
int tt;
scanf("%d",&tt);
while(tt--){solve();}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3772kb
input:
2 5 6 4 1 2 1 30 2 3 1 50 2 5 5 50 3 4 6 10 2 4 5 30 2 5 1 40 1 70 6 100 5 40 1 30 3 1 1 2 3 1 10 1 100
output:
11011 100
result:
ok 2 lines
Test #2:
score: -100
Runtime Error
input:
1110 46 80 30 44 23 5 46 10 28 1 64 32 34 3 40 9 36 1 26 15 14 5 95 38 19 2 34 2 17 4 183 10 38 2 81 5 15 2 83 31 38 3 100 40 30 1 53 41 10 1 193 29 20 5 18 14 41 3 78 8 16 5 74 46 13 3 78 44 28 3 45 1 40 3 133 5 32 1 108 22 26 2 83 10 38 1 77 11 40 1 11 17 21 2 66 41 46 3 98 9 36 2 25 40 18 1 19 27...