QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#710719 | #9431. The Quest for El Dorado | libantian | WA | 153ms | 36924kb | C++23 | 4.0kb | 2024-11-04 21:12:10 | 2024-11-04 21:12:11 |
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],se;
bool st[N]; int T;
////////////////////////////////////////////
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;
///////
vector<Node>add;
vector<pii>addk;
/////
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;
add.push_back({x,y,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;
addk.push_back({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();
if(T==2){
for(int i=1;i<=n;i++){
if(dist[i].fi==INF)cout<<0;
else cout<<1;
}
cout<<endl;
}else if(se==10){
cout<<n<<" "<<m<<" "<<k<<endl;
for(auto v:add)cout<<v.to<<" "<<v.c<<" "<<v.len<<" ";
cout<<endl;
for(auto v:addk)cout<<v.fi<<" ";
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cout << setiosflags(ios::fixed) << setprecision(15);
T=1;
cin>>T;
for(se=1;se<=T;se++)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 32256kb
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: 36924kb
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:
43 80 80 28 42 100 6 3 198 26 32 289 14 38 76 37 30 67 21 40 134 21 40 138 14 38 74 4 1 90 33 24 120 27 41 45 29 26 45 33 3 21 22 15 21 10 9 77 4 34 399 11 42 5 17 8 76 24 25 4 34 30 386 22 16 65 20 2 67 12 9 79 18 7 42 37 39 46 6 22 109 21 42 277 2 23 3 17 8 72 35 10 66 19 21 68 40 23 198 10 38 92 ...
result:
wrong answer 1st lines differ - expected: '1000110011110111110010100001010100100101000000', found: '43 80 80'