QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#54622 | #4188. Excursion to Porvoo | Username# | WA | 93ms | 74504kb | C++ | 1.7kb | 2022-10-09 21:11:50 | 2022-10-09 21:11:52 |
Judging History
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'