QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#735669 | #9431. The Quest for El Dorado | Nana7 | RE | 27ms | 287268kb | C++14 | 2.9kb | 2024-11-11 21:12:04 | 2024-11-11 21:12:04 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
#define I inline
#define int long long
using namespace std;
const int N = 500010;
struct Dat {
int tim,dis,id;
Dat(int _tim=0,int _dis=0,int _id=0) {
tim=_tim; dis=_dis; id=_id;
}
bool operator > (const Dat &t) const {
if(tim==t.tim) return dis<t.dis;
return tim<t.tim;
}
bool operator < (const Dat &t) const {
if(tim==t.tim) return dis>t.dis;
return tim>t.tim;
}
};
struct edge {
int u,c,l;
edge(int _t=0,int _c=0,int _l=0) {
u=_t; c=_c; l=_l;
}
};
struct tic {
int a,b;
}a[N];
priority_queue<Dat> pq;
vector<edge> q[N];
vector<int> v[N],id[N],f[20][N];
int n,m,K,lg[N];
int vis[N];
Dat dis[N];
I bool big(Dat d1,Dat d2) {
if(d1.tim>d2.tim) return 1;
if(d1.dis>d2.dis) return 1;
}
I void pdeal() {
for(int i=1;i<=m;++i) v[i].clear(),id[i].clear();
for(int i=1;i<=m;++i)
for(int j=0;j<=19;++j)
f[i][j].clear();
for(int i=1;i<=K;++i) {
int c=a[i].a,l=a[i].b;
v[c].push_back(l);
id[c].push_back(i);
for(int j=0;j<=19;++j)
f[c][j].push_back(l);
}
//cout<<"???"<<endl;
for(int co=1;co<=m;++co) {
// cout<<"As"<<co<<' '<<v[co].size()<<endl;
for(int j=0;j<19;++j) {
for(int i=1;i+(1<<j)<=v[co].size();++i) {
f[co][j+1][i-1]=max(f[co][j][i-1],f[co][j][i+(1<<j)-1]);
}
}
}
}
I int query(int col,int tim,int len) {
int p=lower_bound(id[col].begin(),id[col].end(),tim)-id[col].begin();
if(p==id[col].size()) return -1;
for(int i=19;i>=0;--i) {
if(p+(1<<i)<=id[col].size()-1&&f[col][i][p]<len) p=p+(1<<i);
}
if(v[col][p]>=len) return id[col][p];
else return -1;
}
I void dij() {
for(int i=1;i<=n;++i) dis[i]=Dat(1e9,1e9,i),vis[i]=0;
dis[1]=Dat(0,0,1); vis[1]=1;
pq.push(dis[1]);
while(!pq.empty()) {
Dat k=pq.top(); pq.pop();
int x=k.id;
for(auto &t:q[x]) {
int u=t.u,c=t.c,l=t.l;
if(a[k.tim].a==c&&l+k.dis<=a[k.tim].b) {
Dat upd=Dat(k.tim,k.dis+l,u);
if(big(dis[u],upd)) {
dis[u]=upd;
if(!vis[u]) {
vis[u]=1;
pq.push(dis[u]);
}
}
} else {
int mk=query(c,k.tim+1,l);
if(mk==-1) continue;
Dat upd=Dat(mk,l,u);
if(big(dis[u],upd)) {
dis[u]=upd;
if(!vis[u] ) {
vis[u]=1;
pq.push(dis[u]);
}
}
}
}
}
}
I void print() {
for(int i=1;i<=n;++i) {
if(dis[i].tim==1e9) cout<<'0';
else cout<<'1';
}
cout<<endl;
}
I void solve() {
cin>>n>>m>>K;
for(int i=1;i<=n;++i) q[i].clear();
for(int i=1;i<=m;++i) {
int u,v,c,l; cin>>u>>v>>c>>l;
q[u].push_back(edge(v,c,l));
q[v].push_back(edge(u,c,l));
}
for(int i=1;i<=K;++i) cin>>a[i].a>>a[i].b;
pdeal();// cout<<"ps1"<<endl;
dij();
print();
}
signed main()
{
int T; cin>>T;
while(T--) {
solve();
}
}
/*
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: 27ms
memory: 287268kb
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
Runtime Error
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...