QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#771387#9431. The Quest for El Doradoda18_WA 60ms536088kbC++146.3kb2024-11-22 12:23:162024-11-22 12:23:18

Judging History

你现在查看的是最新测评结果

  • [2024-11-22 12:23:18]
  • 评测
  • 测评结果:WA
  • 用时:60ms
  • 内存:536088kb
  • [2024-11-22 12:23:16]
  • 提交

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<int>s[20];
	void insert(int x){a.push_back(x);}
	void solve(){
		int L=a.size();
		for(int x:a)s[0].push_back(x);
		for(int j=1;1<<j<=L;j++){
			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){
		if(r>l)return 0;
		int k=__lg(r-l+1);
		return max(s[k][l],s[k][r-(1<<k)+1]);
	}
	void clear(){
		a.clear();
		of(0,19)s[i].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;
	tf(m){
		st[i].clear();
		int x=read(),y=read(),C=read(),V=read();
		add(x,y,C,V);
		add(y,x,C,V);
	}
	tf(k){
		tc[i]=read(),tv[i]=read();
		st[tc[i]].insert(tv[i]);
		V[tc[i]].push_back(i);
	}
	tf(m)V[i].push_back(k+1),st[i].insert(1145141919810),st[i].solve();
	dij();
	nf()putchar(48|!!(d[i].f^k+1));putchar(10);
	if(n>1000)exit(0);
}
signed main(){
	while(T--)solve();
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 60ms
memory: 536088kb

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:

10000
100

result:

wrong answer 1st lines differ - expected: '11011', found: '10000'