QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #771404 | #9431. The Quest for El Dorado | da18_ | WA | 7ms | 89648kb | C++14 | 6.4kb | 2024-11-22 12:35:08 | 2024-11-22 12:35:09 |
Judging History
answer
#include<bits/stdc++.h>
//#pragma comment(linker,"/stack:200000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#define fastcall __attribute__((optimize("-O3")))
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("-fipa-sra")
//#pragma GCC optimize("-ftree-pre")
//#pragma GCC optimize("-ftree-vrp")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("-findirect-inlining")
//#pragma GCC optimize("-fhoist-adjacent-loads")
//#pragma GCC optimize("-foptimize-sibling-calls")
//#pragma GCC optimize("-fexpensive-optimizations")
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse")
//#pragma GCC optimize("-fpeephole2")
//#pragma GCC optimize("inline-functions-called-once")
//#pragma GCC optimize("-fdelete-null-pointer-checks")
//#pragma GCC optimize("-ffast-math")
//#pragma GCC optimize("-fsched-spec")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-freorder-blocks")
//#pragma GCC optimize("-fschedule-insns")
//#pragma GCC optimize("-frerun-cse-after-loop")
//#pragma GCC optimize("inline-small-functions")
//#pragma GCC optimize("-finline-small-functions")
//#pragma GCC optimize("-ftree-switch-conversion")
//#pragma GCC optimize("-fcse-follow-jumps")
//#pragma GCC optimize("-ftree-tail-merge")
//#pragma GCC optimize("-fschedule-insns2")
//#pragma GCC optimize("-fstrict-aliasing")
//#pragma GCC optimize("-falign-jumps")
//#pragma GCC optimize("-fsched-interblock")
//#pragma GCC optimize("-fpartial-inlining")
//#pragma GCC optimize("inline-functions")
//#pragma GCC optimize("-fcrossjumping")
//#pragma GCC optimize("-falign-loops")
//#pragma GCC optimize("-falign-labels")
//#pragma GCC optimize("-fdevirtualize")
//#pragma GCC optimize("-fcaller-saves")
//#pragma GCC optimize("-fthread-jumps")
//#pragma GCC optimize("-funroll-loops")
//#pragma GCC optimize("-falign-functions")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("-freorder-functions")
using namespace std;
#define ll long long
#define int ll
#define pint pair<int,int>
#define f first
#define s second
#define mp make_pair
#define aF(begin,end,step,name) for(int name=begin;name<=end;name+=step)
#define oF(B,E,N) aF(B,E,1,N)
#define af(B,E,S) aF(B,E,S,i)
#define of(B,E) af(B,E,1)
#define tF(E,N) oF(1,E,N)
#define tf(E) of(1,E)
#define nF(N) tF(n,N)
#define nf() tf(n)
#define mF(N) tF(m,N)
#define mf() tf(m)
#define GF(x,ep) for(int ep=h[x];ep;ep=nxt[ep])
#define Gf(x) GF(x,ep)
#define gF(ep) GF(x,ep)
#define gf() Gf(x)
#define X 2147483647
#define X20 1048575
#define file(x) (freopen(#x".in","r",stdin),freopen(#x".out","w",stdout))
#define READ(x) (file(x),read())
#define Read(x) (freopen(#x".in","r",stdin),read())
inline ll read(){
ll x=0;
short f=1;
char c=getchar();
while(c>57||c<48){
if(c==45) f=-1;
c=getchar();
}
while(c<58&&c>47){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
inline ll readf(int T){
ll x=0;
short f=1;
char c=getchar();
while(c>57||c<48){
if(c==45) f=-1;
c=getchar();
}
while(c<58&&c>47){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
x*=T;
if(c^'.') return x*f;
c=getchar();
while(c<58&&c>47){
x+=(c^48)*(T/=10);
c=getchar();
}
return x*f;
}
inline void write(ll x){
if(x<0ll) putchar(45),x=~x+1;
if(x>9ll) write(x/10);
putchar(x%10|48);
}
inline void writen(ll x,int w){
if(w>1) writen(x/10,w-1);
putchar(x%10|48);
}
inline void writeb(ll x,int base=10){
if(x<0ll) putchar(45),x=~x+1;
if(x>=base) writeb(x/base,base);
putchar(x%base|48);
}
inline void writebn(ll x,int w,int base=10){
if(w>1) writebn(x/base,w-1,base);
putchar(x%base|48);
}
inline char gtch(){
char c=getchar();
while(c<33) c=getchar();
return c;
}
#define mod 998244353
int fp(int a,ll b,int p=mod){
int ans=1,base=a;
while(b){
if(b&1) (ans*=base)%=p;
(base*=base)%=p;
b>>=1;
}
return ans;
}
int T=read();
int h[1000005],to[2000005],nxt[2000005],v[2000005],c[2000005],tyc;
void add(int x,int y,int z,int zz){
to[++tyc]=y;
nxt[tyc]=x[h];
x[h]=tyc;
c[tyc]=z;
v[tyc]=zz;
}
int tc[1000005],tv[1000005];
struct ST{
vector<int>a;
vector<vector<int>>s;
void insert(int x){a.push_back(x);}
void solve(){
int L=a.size();
s.push_back(a);
for(int j=1;1<<j<=L;j++){
s.push_back(vector<int>(0));
for(int i=0;i+(1<<j)<=L;i++){
s[j].push_back(max(s[j-1][i],s[j-1][i+(1<<j-1)]));
}
}
}
int query(int l,int r){
int k=__lg(r-l+1);
if(s.size()<=k)exit(0);
if(s[k].size()<=r-(1<<k)+1)exit(0);
return max(s[k][l],s[k][r-(1<<k)+1]);
}
void clear(){
a.clear();
s.clear();
}
};
ST st[1000005];
vector<int> V[1000005];
int find(int c,int l,int v){
int L=lower_bound(begin(V[c]),end(V[c]),l)-begin(V[c]),lp=L,rp=V[c].size()-1,ans=rp;
while(lp<=rp){
int mid=lp+rp>>1;
if(st[c].query(L,mid)>=v)rp=(ans=mid)-1;
else lp=mid+1;
}
return V[c][ans];
}
pint d[1000005];
int vis[1000005];
int n,m,k;
void dij(){
of(2,n)d[i]=mp(k+1,vis[i]=0);
vis[1]=0;
priority_queue<pair<pint,int>,vector<pair<pint,int>>,greater<pair<pint,int>>>q;
q.push(mp(d[1],1));
while(q.size()){
int x=q.top().s;q.pop();
if(vis[x])continue;
vis[x]=1;
// printf("%d:%d %d\n",x,d[x].f,d[x].s);
gf(){
// printf("??%d-->%d\n",x,to[ep]);
if(!vis[to[ep]]){
// printf("ec:%d,(nowc:%d,)ev:%d,(resv:%d,)\n",c[ep],tc[d[x].f],v[ep],tv[d[x].f]-d[x].s);
if(c[ep]==tc[d[x].f]&&tv[d[x].f]-d[x].s>=v[ep]&&d[to[ep]]>=mp(d[x].f,d[x].s+v[ep])){
// printf("!!%d-->%d\n",x,to[ep]);
q.push(mp(d[to[ep]]=mp(d[x].f,d[x].s+v[ep]),to[ep]));
}
else{
int $=find(c[ep],d[x].f+1,v[ep]);
if($!=n+1&&d[to[ep]]>=mp($,v[ep])){
// printf(" !%d-->%d\n",x,to[ep]);
q.push(mp(d[to[ep]]=mp($,v[ep]),to[ep]));
}
}
}
}
}
}
void solve(){
n=read(),m=read(),k=read();
tyc=0;
nf()h[i]=0;
// cerr<<'1'<<'\n';
tf(m){
st[i].clear();
int x=read(),y=read(),C=read(),V=read();
add(x,y,C,V);
add(y,x,C,V);
}
// cerr<<'1'<<'\n';
tf(k){
tc[i]=read(),tv[i]=read();
st[tc[i]].insert(tv[i]);
V[tc[i]].push_back(i);
}
// cerr<<'1'<<'\n';
tf(m)V[i].push_back(k+1),st[i].insert(1145141919810),st[i].solve();
// cerr<<'1'<<'\n';
dij();
// cerr<<'1'<<'\n';
nf()putchar(48|!!(d[i].f^k+1));putchar(10);
// cerr<<'1'<<'\n';
}
signed main(){
while(T--)solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 7ms
memory: 89648kb
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: 4ms
memory: 89648kb
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
result:
wrong answer 2nd lines differ - expected: '1100010010111011011011000000011000001100001000', found: ''