QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#781211 | #9431. The Quest for El Dorado | hotdogseller | WA | 19ms | 25576kb | C++14 | 3.9kb | 2024-11-25 15:15:34 | 2024-11-25 15:15:35 |
Judging History
answer
#include<bits/stdc++.h>
#define maxn 500005
#define INF 1e18
#define int long long
using namespace std;
inline int read(){
int lre=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-'){
f=-1;
}
c=getchar();
}
while(isdigit(c)){
lre=(lre<<3)+(lre<<1)+(c-'0');
c=getchar();
}
return lre*f;
}
struct edge{
int to;
int val;
int c;
int next;
}e[2*maxn];
int e_cnt=1,head[maxn];
void add(int u,int v,int w,int c){
e[e_cnt].to=v;
e[e_cnt].val=w;
e[e_cnt].c=c;
e[e_cnt].next=head[u];
head[u]=e_cnt++;
}
int n,m,k;
int a[maxn],b[maxn];
pair<int,int> dis[maxn];//{用到的票,路程}
struct node{
int x;
pair<int,int> val;
};
node make_node(int x,int v1,int v2){
node lre;lre.x=x;
lre.val=make_pair(v1,v2);
return lre;
}
bool operator <(node a,node b){
if(a.val.first==b.val.first){
return a.val.second>b.val.second;
}
return a.val.first>b.val.first;
}
priority_queue<node> pq;
bool okay(pair<int,int> p1,pair<int,int> p2){
if(p1.first==p2.first){
return p1.second<p2.second;
}
return p1.first<p2.first;
}//p1是否比p2更优
int tot=1;
const int L=1,R=1e9;
int root[maxn];
int lc[2*maxn],rc[2*maxn],p[2*maxn];
void change(int x1,int x2,int l,int r,int goal,int val){
if(l==r){
p[x2]=val;
return;
}
int mid=l+r>>1;
if(goal<=mid){
rc[x2]=rc[x1];
lc[x2]=tot++;lc[lc[x2]]=rc[lc[x2]]=0;
change(lc[x1],lc[x2],l,mid,goal,val);
}else{
lc[x2]=lc[x1];
rc[x2]=tot++;lc[rc[x2]]=rc[rc[x2]]=0;
change(rc[x1],rc[x2],mid+1,r,goal,val);
}
}
int query(int x,int l,int r,int goal){
// cout<<"x="<<x<<" of ["<<l<<","<<r<<"]"<<endl;
if(l==r){
return p[x];
}
int mid=l+r>>1;
if(goal<=mid){
if(lc[x]==0)return 0;
return query(lc[x],l,mid,goal);
}else{
if(rc[x]==0)return 0;
return query(rc[x],mid+1,r,goal);
}
}
void show_tree(int x,int l,int r){
cout<<"x="<<x<<" of ["<<l<<","<<r<<"]"<<endl;
if(l!=r){
int mid=l+r>>1;
if(lc[x])show_tree(lc[x],l,mid);
if(rc[x])show_tree(rc[x],mid+1,r);
}else{
cout<<"p="<<p[x]<<endl;
}
}
void solve(){
e_cnt=1;tot=1;
lc[0]=rc[0]=0;p[0]=0;
n=read();m=read();k=read();
for(int i=1;i<=n;i++){
head[i]=0;dis[i]=make_pair(INF,INF);
}
for(int i=1;i<=m;i++){
int u=read(),v=read(),c=read(),l=read();
add(u,v,l,c);add(v,u,l,c);
}
for(int i=1;i<=k;i++){
a[i]=read();b[i]=read();
}
root[k]=0;
for(int i=k-1;i>=1;--i){
root[i]=tot++;lc[root[i]]=rc[root[i]]=0;
change(root[i+1],root[i],L,R,a[i+1],i+1);
// cout<<"show_tree "<<i<<endl;
// show_tree(root[i],L,R);
}
pq.push(make_node(1,1,0));
dis[1].first=1;dis[1].second=0;
while(!pq.empty()){
int x=pq.top().x;pair<int,int> val=pq.top().val;pq.pop();
if(okay(dis[x],val))continue;
// cout<<"x="<<x<<endl;
for(int i=head[x];i;i=e[i].next){
int v=e[i].to,w=e[i].val,c=e[i].c;
pair<int,int> nxt=val;
// cout<<" to "<<v<<" for edge {"<<w<<","<<c<<"}"<<endl;
if(c==a[dis[x].first]&&w+dis[x].second<=b[dis[x].first]){
nxt.second+=w;
if(okay(nxt,dis[v])){
dis[v]=nxt;
pq.push(make_node(v,nxt.first,nxt.second));
}
}else{
// cout<<"query in tree "<<val.first<<" for "<<c<<endl;
nxt.first=query(root[val.first],L,R,c);
// cout<<"change to "<<nxt.first<<endl;
nxt.second=w;
//换票
if(nxt.first&&w<=b[nxt.first]){
if(okay(nxt,dis[v])){
dis[v]=nxt;
pq.push(make_node(v,nxt.first,nxt.second));
}
}
}
}
}
// for(int i=1;i<=n;i++){
// cout<<"{"<<dis[i].first<<","<<dis[i].second<<"} ";
// }
// cout<<endl;
for(int i=1;i<=n;i++){
if(dis[i].first==INF){
putchar('0');
}else{
putchar('1');
}
}
putchar('\n');
}
signed main(){
int t=read();
while(t--){
solve();
}
return 0;
}
/*
1
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
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 20072kb
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: 19ms
memory: 25576kb
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:
1000000000000100000010000000000100000100000000 1000000000000001000000000000000000000000000000 1000000000000000000000000000000000000000000000 1001000000000000000000000010000000000000000000 1000000000000000000000000000000000000000000000 1001100010000000100000000000000001001010010 100000000000000000000...
result:
wrong answer 1st lines differ - expected: '1000110011110111110010100001010100100101000000', found: '1000000000000100000010000000000100000100000000'