QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#718526 | #9431. The Quest for El Dorado | triccsr | WA | 102ms | 30552kb | C++20 | 4.0kb | 2024-11-06 20:44:41 | 2024-11-06 20:44:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+11;
typedef long long LL;
// #define int LL
const int inf=0x3f3f3f3f;
const LL llinf=1e18;
struct E{
int to,c;
LL len;
};
struct H{
int cnt;
LL dis;
int index;
bool operator<(const H &h)const{
if(cnt!=h.cnt)return cnt>h.cnt;
if(dis!=h.dis)return dis>h.dis;
return index>h.index;
}
};
class SegmentTree{
#define ls(x) ((x)<<1)
#define rs(x) (((x)<<1)|1)
#define mid ((l+r)>>1)
vector<LL> mx;
void update(int now){
mx[now]=max(mx[ls(now)],mx[rs(now)]);
}
void build(int l,int r,int now,const vector<LL> & a){
if(l==r){
mx[now]=a[l];
return;
}
build(l,mid,ls(now),a);
build(mid+1,r,rs(now),a);
update(now);
}
int first_geq(int l,int r,int now,int st,int en,LL v){
if(st<=l&&r<=en){
if(mx[now]<v)return -1;
if(l==r)return l;
if(mx[ls(now)]>=v)return first_geq(l,mid,ls(now),st,en,v);
return first_geq(mid+1,r,rs(now),st,en,v);
}
int ret=-1;
if(st<=mid){
ret=first_geq(l,mid,ls(now),st,en,v);
}
if(ret==-1&&en>mid){
ret=first_geq(mid+1,r,rs(now),st,en,v);
}
return ret;
}
public:
int n;
SegmentTree()=default;
SegmentTree(const vector<LL> &vec):n((int)vec.size()){
mx.resize(4*n+1);
build(0,n-1,1,vec);
}
int first_geq(int st,LL v){
if(st>=n)return -1;
return first_geq(0,n-1,1,st,n-1,v);
}
#undef ls
#undef rs
#undef mid
};
int n,m,k;
int a[N];
LL b[N];
bool ok[N];
int cnt[N];
LL dis[N];
vector<E> e[N];
vector<int> cp[N];
SegmentTree sgt[N];
int it[N];
void work(){
cin>>n>>m>>k;
for(int i=1;i<=n;++i){
e[i].clear();
ok[i]=false;
cnt[i]=inf;
dis[i]=llinf;
}
for(int i=1;i<=m;++i){
cp[i].clear();
it[i]=0;
}
for(int i=1;i<=m;++i){
int u,v,c;
LL l;
cin>>u>>v>>c>>l;
e[u].emplace_back((E){v,c,l});
e[v].emplace_back((E){u,c,l});
}
for(int i=1;i<=k;++i){
cin>>a[i]>>b[i];
cp[a[i]].push_back(i);
}
for(int i=1;i<=m;++i){
if(cp[i].empty())continue;
vector<LL> dd;
dd.resize(cp[i].size());
for(int j=0;j<(int)cp[i].size();++j){
dd[j]=b[cp[i][j]];
}
sgt[i]=SegmentTree(dd);
}
priority_queue<H> pq;
cnt[1]=1;
dis[1]=0;
pq.push((H){.cnt=1,.dis=0,.index=1});
for(int loop=1;loop<=n;++loop){
while(!pq.empty()&&ok[pq.top().index])pq.pop();
if(pq.empty())break;
int now=pq.top().index;
pq.pop();
ok[now]=true;
int nowc=a[cnt[now]];
for(auto [to,c,len]:e[now]){
if(ok[to])continue;
int newcnt=inf;
LL newdis=llinf;
if(nowc==c&&dis[now]+len<=b[cnt[now]]){
newcnt=cnt[now];
newdis=dis[now]+len;
}
else{
while(it[c]!=(int)cp[c].size()&&cp[c][it[c]]<=cnt[now])++it[c];
int tmp=sgt[c].first_geq(it[c],len);
if(it[c]==(int)cp[c].size()&&tmp!=-1){
printf("%d %d %d %d\n",c,cp[c].size(),sgt[c].n,tmp);
}
if(tmp!=-1){
newcnt=cp[c][tmp];
newdis=len;
}
}
if(newcnt<cnt[to]||(newcnt==cnt[to]&&newdis<dis[to])){
cnt[to]=newcnt;
dis[to]=newdis;
pq.emplace((H){cnt[to],dis[to],to});
}
}
}
for(int i=1;i<=n;++i){
if(cnt[i]!=inf)printf("1");
else printf("0");
}
printf("\n");
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin>>T;
while(T--){
work();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 30388kb
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
Wrong Answer
time: 102ms
memory: 30552kb
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...
output:
1000110011110111110010100001010100100101000000 1100010010111011011011000000011000001100001000 1000000000000000000000000000000000000000000000 1011010000000010000100010011000100000000000010 1000000000000000000000101000010000001001000001 1001100010110000100001100000000011001110110 101010000000000000010...
result:
wrong answer 13th lines differ - expected: '1111111111111111111111111111111111111111111111', found: '2 0 3 1'