QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#710694 | #9431. The Quest for El Dorado | libantian | WA | 153ms | 43788kb | C++23 | 3.7kb | 2024-11-04 21:03:44 | 2024-11-04 21:03:44 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int,int>
#define pir pair<pii,int>
#define fi first
#define se second
#define all(_a) _a.begin(), _a.end()
struct Node
{
int to,c,len;
};
const int N=500010;
vector<Node>g[N];
set<array<int,3>> s[N];
pii dist[N];
int l[N],r[N],a[N],t[N],ft[N];
bool st[N];
////////////////////////////////////////////
struct node
{
int l, r;
int v; // 区间[l, r]中的最大值
}tr[N * 4];
void pushup(int u) // 由子节点的信息,来计算父节点的信息
{
tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}
void build(int u, int l, int r)
{
tr[u] = {l, r};
if (l == r) {
tr[u].v=a[l];
return;
}
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
int query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) return tr[u].v; // 树中节点,已经被完全包含在[l, r]中了
int mid = tr[u].l + tr[u].r >> 1;
int v = 0;
if (l <= mid) v = query(u << 1, l, r);
if (r > mid) v = max(v, query(u << 1 | 1, l, r));
return v;
}
////////////////////////////////////////
void dij(){
dist[1].fi=0;
priority_queue<pir,vector<pir>,greater<pir>>q;
q.push({dist[1],1});
while(q.size()){
int u=q.top().se;
q.pop();
if(st[u])continue;
st[u]=true;
for(auto ne:g[u]){
int v=ne.to;
int c=ne.c;
int len=ne.len;
if(t[dist[u].fi]==c&&len<=dist[u].se){
pii p={dist[u].fi,dist[u].se-len};
if(p<dist[v]){
dist[v]=p;
q.push({dist[v],v});
}
continue;
}
if(s[c].empty())continue;
auto it=s[c].lower_bound({dist[u].fi,INF,INF});
if(it==s[c].end())continue;
int L=l[c]+(*it)[1],R=r[c];
if(query(1,L,R)<len)continue;
{
int l=L,r=R;
while(l<r){
int mid=l+r>>1;
if(query(1,L,mid)>=len)r=mid;
else l=mid+1;
}
pii p={ft[r],query(1,L,r)-len};
if(p<dist[v]){
dist[v]=p;
q.push({dist[v],v});
}
}
}
}
}
////////////////////////////////////////
void solve(){
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
dist[i].fi=INF;
st[i]=false;
g[i].clear();
}
for(int i=1;i<=m;i++){
s[i].clear();
l[i]=r[i]=0;
}
for(int i=1;i<=m;i++){
int x,y,c,len;
cin>>x>>y>>c>>len;
g[x].push_back({y,c,len});
g[y].push_back({x,c,len});
}
for(int i=1;i<=k;i++){
int c,len;
cin>>c>>len;
s[c].insert({i,(int)s[c].size(),len});
t[i]=c;
}
int len=0;
for(int i=1;i<=m;i++){
if(s[i].empty())continue;
l[i]=len+1;
r[i]=len+s[i].size();
for(auto v:s[i]){
int x=v[2];
a[++len]=x;
ft[len]=v[0];
}
}
build(1,1,len);
dij();
for(int i=1;i<=n;i++){
if(dist[i].fi==INF)cout<<0;
else cout<<1;
}
cout<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cout << setiosflags(ios::fixed) << setprecision(15);
int T;
T=1;
cin>>T;
while(T--)solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 38416kb
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: 153ms
memory: 43788kb
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 10th lines differ - expected: '1001100111010000100000000110100000010000001', found: '1001100110010000100000000110100000010000001'