QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#54622#4188. Excursion to PorvooUsername#WA 93ms74504kbC++1.7kb2022-10-09 21:11:502022-10-09 21:11:52

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-09 21:11:52]
  • 评测
  • 测评结果:WA
  • 用时:93ms
  • 内存:74504kb
  • [2022-10-09 21:11:50]
  • 提交

answer

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
const int N = 1e5 + 5;
struct edge {
    int u, d, c;
};
bool cmp(edge x, edge y) {
	return x.c > y.c;
}
struct query {
    int w, ind, st, en, ans;
};
int n, m, q, C[N];
vector<edge> edges;
queue<int> mids[N];
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 0;i < m;i++) {
		int x, d, c;
		cin >> x >> d >> c;
		edges.push_back({x, d, c});
	}
	sort(edges.begin(), edges.end(), cmp);
	cin >> q;
	vector<query> queries(q);
	for(int i = 0;i < q;i++) {
		int w;
		cin >> w;
		queries[i] = {w, i, 0, m - 1, -1};
	}
	while(1) {
		bool found = false;
		for(int i = 1;i <= n;i++)
			C[i] = 2e4;
		for(int i = 0;i < q;i++) {
			if(queries[i].st > queries[i].en)
				continue;
			int mid = queries[i].st + queries[i].en >> 1;
			mids[mid].push(i);
			found = true;
		}
		if(!found)
			break;
		int ans = (n - 1) * 2e4, cnt = 0;
		for(int i = 0;i < m;i++) {
			int u = edges[i].u;
			int d = edges[i].d;
			if(C[u] > d) {
				if(C[u] == 2e4)
					cnt++;
				ans -= C[u];
				C[u] = d;
				ans += C[u];
			}
			while(mids[i].size()) {
				int cur = mids[i].front();
				mids[i].pop();
				if(queries[cur].w > edges[i].c)
					queries[cur].en = i - 1;
				else if(cnt == n - 1)
					queries[cur].ans = ans, queries[cur].st = i + 1;
				else
					queries[cur].en = i - 1;
			}
		}
	}	
	for(int i = 0;i < q;i++) {
		if(queries[i].ans == -1)
			cout << "impossible\n";
		else
			cout << queries[i].ans << '\n';
	}
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 19ms
memory: 70744kb

input:

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

output:

impossible
impossible
100
1
1

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 16ms
memory: 70752kb

input:

5 7
1 200 30
2 200 31
3 200 32
4 200 33
1 5000 33
2 5000 33
3 5000 33
3
30
31
33

output:

800
5600
15200

result:

ok 3 lines

Test #3:

score: 0
Accepted
time: 23ms
memory: 70832kb

input:

2 3
1 3 3
1 4 2
1 2 1
3
1
3
2

output:

2
3
3

result:

ok 3 lines

Test #4:

score: -100
Wrong Answer
time: 93ms
memory: 74504kb

input:

100000 99999
1 8793 670998
2 3301 949483
3 5662 542705
4 3033 907487
5 7035 366434
6 5771 1750
7 2575 80336
8 5163 613257
9 5748 414726
10 4990 119039
11 5855 239538
12 1965 755221
13 8891 149341
14 3213 674329
15 9189 660274
16 4593 513364
17 793 326875
18 2873 954337
19 3470 105349
20 9374 779965
...

output:

impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
impossible
imp...

result:

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