QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#145116#4188. Excursion to Porvoovalue0WA 1ms3700kbC++201.4kb2023-08-21 22:06:532023-08-21 22:06:56

Judging History

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

  • [2023-08-21 22:06:56]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3700kb
  • [2023-08-21 22:06:53]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
#define fi first
#define se second
typedef pair<int,int> pii;
typedef pair<int,pair<int,int>> piii;
int n,m; 

struct Edge
{
	int idx;
	ll d;
	ll w;
	
	bool operator < (Edge t)
	{
		return w < t.w;
	}
};

int main()
{
	scanf("%d %d",&n,&m);
	vector<Edge> v;
	vector<ll> dist(n + 1,1e18);
	unordered_map<int,bool> st;
	for(int i = 1;i<=m;i++)
	{
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		v.push_back({a,b,c});
	}
	sort(v.begin(),v.end());
	int k;
	scanf("%d",&k);
	vector<pii> q;
	for(int i = 1;i<=k;i++)
	{
		int x;
		scanf("%d",&x);
		q.push_back({x,i});
	}
	sort(q.begin(),q.end());
	reverse(q.begin(),q.end());
	int j = v.size() - 1;
	ll res = 0;
	vector<ll> ans(k + 1);
	for(int i = 0;i<q.size();i++)
	{
//		cout<<q[i].fi<<' '<<j<<' '<<v[j].w<<endl;
		while(j >= 0 && q[i].fi <= v[j].w)
		{
			int idx = v[j].idx;
			if(!st.count(idx))
			{
				res += v[j].d;
				st[idx] = true;
				dist[idx] = v[j].d;
			}
			else if(dist[idx] > v[j].d)
			{
				res += v[j].d - dist[idx];
			}
			j --;
		}
//		cout<<i<<' '<<res<<endl;
		if(st.size() != n - 1)
		{
			ans[q[i].se] = -1;
		}
		else
		{
			ans[q[i].se] = res;
		}
	}
	for(int i = 1;i<=k;i++)
	{
		if(i == -1)
		{
			puts("impossible");
		}
		else
		{
			printf("%lld\n",ans[i]);
		}
	}
	return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3700kb

input:

2 2
1 100 300
1 1 30
5
400
500
300
20
1

output:

-1
-1
100
1
1

result:

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