QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#152246#5458. Shortest Path QueryinvernoWA 115ms22300kbC++141.7kb2023-08-27 20:45:332023-08-27 20:45:36

Judging History

你现在查看的是测评时间为 2023-08-27 20:45:36 的历史记录

  • [2024-06-21 12:38:07]
  • 管理员手动重测本题所有提交记录
  • 测评结果:WA
  • 用时:64ms
  • 内存:22112kb
  • [2023-08-27 20:45:36]
  • 评测
  • 测评结果:0
  • 用时:115ms
  • 内存:22300kb
  • [2023-08-27 20:45:33]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;


const int N = 5e4+10;
int n,m,q;
vector<int> A[N], B[N];
struct node{
    int x,y;
    bool operator < (const node &a)const{
        return x!=a.x?x<a.x:y<a.y;
    }
};
vector<node>p[N], tmp;

void merge(vector<node> &A, const vector<node> &B){
   int i=0, j=0, ta=A.size(), tb=B.size();
   tmp.clear();
   while (i<ta&&j<tb) tmp.push_back(A[i]<B[j]?A[i++]:B[j++]);
   while (i<ta) tmp.push_back(A[i++]);
   while (j<tb) tmp.push_back(B[j++]);
   A.clear();
   for (node x:tmp){
      if (A.empty()) A.push_back(x);
      else if (x.y < A.back().y) {
        for (;A.size()>1;A.pop_back()) {
            node a=A[A.size()-2], b = A.back();
            if ((a.y - b.y) * (b.x - x.x) > (b.y - x.y) * (a.x - b.x))
              break;
        }
        A.push_back(x); 
      }
   }
   for(int i=1;i+1<ta;i++)
	if (!(1.0*(A[i].y-A[i-1].y)/(A[i].x-A[i-1].x)>1.0*(A[i].y-A[i+1].y)/(A[i].x-A[i+1].x))) cout << "Failed2\n";
   return;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    for (int i=1;i<=m;++i){
        int u,v,c;
        cin >> u >> v >> c;
        if (u==v) cout <<"Failed\n";
        if (!c) A[u].push_back(v);
          else B[u].push_back(v);
    }
    p[1].push_back({0,0});
    for (int u=1;u<=n;++u) {
        vector<node> temp = p[u];
        for (auto &x:temp)x.x++;
        for (int v:A[u]) merge(p[v], temp);
        temp = p[u];
        for (auto &x:temp)x.y++;
        for (int v:B[u]) merge(p[v], temp);
    }

    cin >> q;
    for (int i=1;i<=q;++i){
        int a,b,u,ans=1e9;
        cin >>a>>b>>u;
        for (node x:p[u])
          ans = min(ans, a*x.x+b*x.y);
        cout <<ans<<endl;
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 7296kb

input:

4 4
1 2 0
1 3 1
2 4 0
3 4 1
3
3 5 2
3 2 4
2 3 4

output:

3
4
4

result:

ok 3 number(s): "3 4 4"

Test #2:

score: -100
Wrong Answer
time: 115ms
memory: 22300kb

input:

50000 100000
1 2 1
2 3 0
3 4 1
4 5 0
5 6 1
6 7 0
7 8 1
8 9 1
9 10 0
10 11 1
11 12 1
12 13 1
13 14 0
14 15 0
15 16 0
16 17 0
17 18 1
18 19 1
19 20 0
20 21 1
21 22 0
22 23 0
23 24 1
24 25 1
25 26 0
26 27 1
27 28 0
28 29 0
29 30 0
30 31 0
31 32 1
32 33 0
33 34 1
34 35 1
35 36 1
36 37 1
37 38 0
38 39 0
...

output:

Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Failed2
Fail...

result:

wrong output format Expected integer, but "Failed2" found