| 记录编号 |
326341 |
评测结果 |
AAAWEETTTT |
| 题目名称 |
零食店 |
最终得分 |
30 |
| 用户昵称 |
 AntiLeaf |
是否通过 |
未通过 |
| 代码语言 |
C++ |
运行时间 |
5.907 s |
| 提交时间 |
2016-10-21 07:26:39 |
内存使用 |
0.54 MiB |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
/*struct tree{
#define siz(x) ((x)?((x)->size):(0))
static const double BAL=0.65;
static const int maxn=100010;
struct node{//Scapegoat Tree
int data,size;
node *lc,*rc,*prt;
node(int d):data(d),size(1),lc(NULL),rc(NULL),prt(NULL){}
inline void refresh(){size=siz(lc)+siz(rc)+1;}
}*root;
int data[maxn],cnt;
tree(){root=NULL;}
void clear(){
removetree(root);
root=NULL;
}
void insert(int x){
node *rt=insert(new node(x));
if(rt)rebuild(rt);
}
void erase(int x){
node *rt=erase(find(x));
if(rt)rebuild(rt);
}
int rank(int x){
node *rt=root;
int ans=0;
while(rt){
if(x<=rt->data)rt=rt->lc;
else{
ans+=siz(rt->lc)+1;
rt=rt->rc;
}
}
return ans;
}
node *insert(node *x){
if(!root){
root=x;
return NULL;
}
node *rt=root;
for(;;){
if(x->data<rt->data){
if(rt->lc)rt=rt->lc;
else{
rt->lc=x;
break;
}
}
else{
if(rt->rc)rt=rt->rc;
else{
rt->rc=x;
break;
}
}
}
x->prt=rt;
x=NULL;
while(rt){
rt->refresh();
if(max(siz(rt->lc),siz(rt->rc))>BAL*rt->size)x=rt;
rt=rt->prt;
}
return x;
}
node *find(int x){
node *rt=root;
while(rt){
if(x==rt->data)return rt;
else if(x<rt->data)rt=rt->lc;
else rt=rt->rc;
}
return NULL;
}
node *erase(node *x){
if(x->lc&&x->rc){
node *y=findmax(x->lc);
x->data=y->data;
return erase(y);
}
if(!x->lc&&!x->rc){
if(x->prt){
if(x==x->prt->lc)x->prt->lc=NULL;
else x->prt->rc=NULL;
}
else root=NULL;
}
else if(x->lc&&!x->rc){
x->lc->prt=x->prt;
if(x->prt){
if(x==x->prt->lc)x->prt->lc=x->lc;
else x->prt->rc=x->lc;
}
else root=x->lc;
}
else if(!x->lc&&x->rc){
x->rc->prt=x->prt;
if(x->prt){
if(x==x->prt->lc)x->prt->lc=x->rc;
else x->prt->rc=x->rc;
}
else root=x->rc;
}
node *rt=x->prt;
delete x;
x=NULL;
while(rt){
rt->refresh();
if(max(siz(rt->lc),siz(rt->rc))>BAL*rt->size)x=rt;
rt=rt->prt;
}
return x;
}
void rebuild(node *rt){
cnt=0;
zorder(rt);
node *x=rebuild(1,cnt);
x->prt=rt->prt;
if(rt->prt){
if(rt==rt->prt->lc)rt->prt->lc=x;
else rt->prt->rc=x;
}
else root=x;
removetree(rt);
}
void zorder(node *x){
if(!x)return;
zorder(x->lc);
data[++cnt]=x->data;
zorder(x->rc);
}
node *rebuild(int l,int r){
if(l>r)return NULL;
if(l==r)return new node(data[l]);
int mid=(l+r)>>1;
node *x=new node(data[mid]);
x->lc=rebuild(l,mid-1);
if(x->lc)x->lc->prt=x;
x->rc=rebuild(mid+1,r);
if(x->rc)x->rc->prt=x;
x->refresh();
return x;
}
void removetree(node *x){
if(!x)return;
removetree(x->lc);
removetree(x->rc);
delete x;
}
node *findmax(node *x){
while(x->rc)x=x->rc;
return x;
}
#undef siz
}T;*/
using namespace __gnu_pbds;
const int maxn=110,maxe=10010;
tree<int,null_mapped_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>T;
struct edge{int to,prev,w;}e[maxe<<1];
struct Q{
int c,d,id;
Q(int c,int d,int id):c(c),d(d),id(id){}
bool operator<(const Q &q)const{return c<q.c;}
};
void addedge(int,int,int);
void work(int);
void SPFA(int);
int n,m,k,last[maxn]={0},len=0,w[maxn],t[maxn],rnk[maxn]={0},ans[maxn],dis[maxn];
vector<Q>qu[maxn];
queue<int>q;
bool inq[maxn]={0};
int main(){
#define MINE
#ifdef MINE
freopen("snackstore.in","r",stdin);
freopen("snackstore.out","w",stdout);
#endif
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++){
scanf("%d",&w[i]);
t[i]=w[i];
}
sort(t+1,t+n+1);
for(int i=1;i<=n;i++){
int p=lower_bound(t+1,t+n+1,w[i])-t;
while(rnk[p])p++;
rnk[p]=i;
}
//for(int i=1;i<=n;i++)printf("%d ",rnk[i]);printf("\n");
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
addedge(x,y,z);
addedge(y,x,z);
}
for(int i=1;i<=k;i++){
int s,c,d;
scanf("%d%d%d",&s,&c,&d);
qu[s].push_back(Q(c,d,i));
}
for(int i=1;i<=n;i++)work(i);
for(int i=1;i<=k;i++)printf("%d\n",ans[i]);
#ifndef MINE
printf("\n-------------------------DONE-------------------------\n");
for(;;);
#endif
return 0;
}
void addedge(int x,int y,int z){
e[++len].to=y;
e[len].w=z;
e[len].prev=last[x];
last[x]=len;
}
void work(int x){
//printf("work(%d)\n",x);
T.clear();
memset(dis,63,sizeof(dis));
dis[x]=0;
q.push(x);
SPFA(0);
/*for(int i=1;i<=n;i++){
if(dis[i]!=0x3f3f3f3f)printf("%d ",dis[i]);
else printf("INF ");
}printf("\n");*/
vector<Q>&a=qu[x];
sort(a.begin(),a.end());
int cnt=a.size(),cur=1;
for(int i=0;i<cnt;i++){
//printf("i=%d c=%d d=%d\n",i,a[i].c,a[i].d);
while(cur<=n&&w[rnk[cur]]<=a[i].c){
q.push(rnk[cur]);
inq[rnk[cur]]=true;
cur++;
}
SPFA(a[i].c);
/*for(int j=1;j<=n;j++){
if(dis[j]!=0x3f3f3f3f)printf("%d ",dis[j]);
else printf("INF ");
}printf("\n");*/
ans[a[i].id]=T.order_of_key(a[i].d+1);
//ans[a[i].id]=T.rank(a[i].d+1);
}
}
void SPFA(int c){
int x;
while(!q.empty()){
x=q.front();
//assert(q.size()<20);
q.pop();
inq[x]=false;
for(int i=last[x];i;i=e[i].prev)if(dis[e[i].to]>dis[x]+e[i].w){
if(dis[e[i].to]!=0x3f3f3f3f)T.erase(dis[e[i].to]);
dis[e[i].to]=dis[x]+e[i].w;
T.insert(dis[e[i].to]);
//assert(T.size()<10);
if(w[e[i].to]<=c&&!inq[e[i].to]){
inq[e[i].to]=true;
q.push(e[i].to);
}
}
}
}
/*
5 5 2
1 2 3 4 5
1 2 1
1 3 4
2 3 2
1 4 3
2 5 1
1 1 3
2 1 2
Answer:
2
3
*/
/*
5 6 6
7 2 5 1 6
1 2 1
3 1 2
5 4 4
3 5 1
2 3 2
1 5 3
3 1 10
4 7 9
2 6 3
1 3 1
5 7 3
5 7 4
Answer:
3
4
3
1
3
4
*/
/*
本题询问非常多，而在线的话不是时间不够就是附加信息太多无法维护，因此考虑离线。
把询问按起点分类，然后按照c从小到大依次处理各询问，用平衡树维护点的距离，
每次按照新的c重跑SPFA并更新答案。
本来想用pb_ds...然而可重好像要用less_equal，不太保险啊不敢用...
这个平衡树是从普通平衡树抄过来的......
*/