Dij WA 40pts求调
查看原帖
Dij WA 40pts求调
999274
CNS_5t0_0r2楼主2024/12/5 12:55
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 9,M = 1e6 + 9,INF = 0x7f7f7f7f;
int T;
int n,m,L,V;
int ans1,ans2;
int s[N];
struct interval{
	int l,r;
} t[N];
int cnt;
struct edge{
	int to,cost,nex;
} e[M << 2];
int head[N],ecnt;
void addedge(int u,int v,int w){
	ecnt++;
	e[ecnt] = (edge){v,w,head[u]};
	head[u] = ecnt;
}

struct node{
	int d,id;
};
bool operator<(node x,node y){
	return x.d > y.d;
}

int dis[N];
bool vis[N];
priority_queue<node> q;

void dij(int st){
	dis[st] = 0;
	q.push((node){0,st});
	while(!q.empty()){
		node u = q.top();
		int d = u.d,id = u.id;
		q.pop();
		if(vis[id])
			continue;
		vis[id] = true;
		for(int i = head[id];i;i = e[i].nex){
			int v = e[i].to,w = e[i].cost;
			if(dis[v] > dis[id] + w){
				dis[v] = dis[id] + w;
				if(!vis[v])
					q.push((node){dis[v],v});
			}
		}
	}
}

void clear(){
	cnt = ecnt = 0;
	ans1 = ans2 = 0;
	for(int i = 0;i <= L;i++){
		s[i] = 0;
		head[i] = 0;
		vis[i] = false;
		dis[i] = INF;
	}
}
signed main(){
//	freopen("detect2.in","r",stdin);
//	freopen("detect.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> T;
	while(T--){
		cin >> n >> m >> L >> V;
		L++;
		clear();
		for(int i = 1;i <= n;i++){
			int d,v,a;
			cin >> d >> v >> a;
			d++;
			if(a > 0){
				if(v > V){
					t[++cnt] = (interval){d,L};
					continue;
				}
				int q = (V * V - v * v) / (a << 1),r = (V * V - v * v) % (a << 1);
				if(d + q + 1 <= L)
					t[++cnt] = (interval){d + q + 1,L};
			}
			else if(a < 0){
				if(v <= V)
					continue;
				int q = (V * V - v * v) / (a << 1),r = (V * V - v * v) % (a << 1);
				int ed = min(r ? d + q : d + q - 1,L);
				if(d <= ed)
					t[++cnt] = (interval){d,ed};
			}
			else if(v > V)
				t[++cnt] = (interval){d,L};
		}
		for(int i = 1;i <= m;i++){
			int p;
			cin >> p;
			p++;
			s[p]++;
		}
		for(int i = 1;i <= L;i++){
			if(s[i]){
				addedge(i,i - 1,0);
				addedge(i - 1,i,1);
			}
			else{
				addedge(i,i - 1,1);
				addedge(i - 1,i,1);
			}
		}
		for(int i = 1;i <= L;i++)
			s[i] += s[i - 1];
		for(int i = 1;i <= cnt;i++)
			if(s[t[i].r] - s[t[i].l - 1]){
				ans1++;
				addedge(t[i].l - 1,t[i].r,t[i].r - t[i].l);
			}
		dij(0);
		for(int i = 1;i <= L;i++)
			ans2 += (dis[i] - dis[i - 1]) ^ 1;
		ans2 = m - ans2;
		cout << ans1 << ' ' << ans2 << '\n';
	}
	return 0;
}
2024/12/5 12:55
加载中...