QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#754315 | #9431. The Quest for El Dorado | wsxcb | WA | 129ms | 6276kb | C++17 | 2.1kb | 2024-11-16 14:44:43 | 2024-11-16 14:44:44 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
typedef vector<vector<ll>> Mat;
const int N=3e5+10,mod=998244353,inf=2e9+18;
const double pi=acos(-1.0),esp=1e-9;
const ll INF=1e18;
struct node{
int u,col,v1;
ll v2,c;
bool operator<(const node &t)const{
if(v1==t.v1) return t.v2<v2;
return v1<t.v1;
}
};
void solve(){
int n,m,k;
cin>>n>>m>>k;
vector<vector<int>>pos(m+1);
vector<vector<ll>>sum(m+1);
vector<int>vis(n+1);
vector< vector< array<int,3> > >e(n+1);
pair<int,int>sc={inf,inf};
vector<pair<int,int>>dis(n+1,sc);
dis[1]={0,0};
for(int i=1;i<=m;i++){
int u,v,c,l;
cin>>u>>v>>c>>l;
e[u].pb({v,c,l});
e[v].pb({u,c,l});
pos[i].pb(0);
sum[i].pb(0);
}
for(int i=1;i<=k;i++){
int a,b;
cin>>a>>b;
pos[a].pb(i);
sum[a].pb(b);
}
for(int i=1;i<=m;i++){
for(int j=1;j<(int)pos[i].size();j++){
sum[i][j]+=sum[i][j-1];
}
}
priority_queue<node>q;
q.push({1,0,0,0,0});
while(q.size()){
auto [u,col1,v1,v2,c]=q.top();
q.pop();
if(vis[u])continue;
//cout<<u<<' '<<v1<<' '<<v2<<' '<<c<<'\n';
vis[u]=1;
for(auto [v,col2,l]:e[u]){
if(col1==col2&&c>=l){
if(dis[v].fi>v1||(dis[v].fi==v1&&dis[v].se>v2+l))
{
//cout<<v<<' ';
dis[v]={v1,v2+l};
q.push({v,col1,v1,v2+l,c-l});
}
continue;
}
int p1=upper_bound(pos[col2].begin(),pos[col2].end(),v1)-pos[col2].begin();
if(p1==(int)pos[col2].size())continue;
p1--;
int p2=lower_bound(sum[col2].begin(),sum[col2].end(),l+sum[col2][p1])-sum[col2].begin();
if(p2==(int)sum[col2].size())continue;
int x=sum[col2][p2]-sum[col2][p1]-l,z=pos[col2][p2];
int y=l+sum[col2][p1]-sum[col2][p2-1];
if(dis[v].fi>z||(dis[v].fi==z&&dis[v].se>y))
{
dis[v]={z,y};
q.push({v,col2,z,y,x});
//cout<<v<<' ';
}
}
//cout<<'\n';
}
for(int i=1;i<=n;i++){
if(dis[i].fi<=k)cout<<1;
else cout<<0;
}
cout<<'\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t=1;
cin>>t;
while(t--)
solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3552kb
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: 129ms
memory: 6276kb
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:
1110110111110111110010110101011100100101001010 1111010011111111011111110000011111011111011010 1000000000000000000000000000000000000000000000 1111010101111111111110111111100111011011111111 1111000000010000000100101010110001101011000111 1011101010110111111011111011110011111110111 101010100000000000010...
result:
wrong answer 1st lines differ - expected: '1000110011110111110010100001010100100101000000', found: '1110110111110111110010110101011100100101001010'