oj.uz

Submission #696357

# Submission time Handle Problem Language Result Execution time Memory
696357 2023-02-06T09:53:19 Z Cross_Ratio Travelling Merchant (CCO21_day2problem1) C++14
25 / 25
 335 ms 43308 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e18;
vector<array<int, 4>> adj[200005];
int dis[200005];
int A[200005];
struct SegTree {
    vector<int> seg;
    int MAX;
    void init(int N) {
        int i;
        for(i=1;i<2*N;i*=2) {}
        seg.resize(i);
        MAX = i;
        for(i=0;i<MAX;i++) seg[i] = INF;
    }
    void Edit(int n, int a) {
        n += MAX/2;
        seg[n] = a;
        n /= 2;
        while(n) {
            seg[n] = min(seg[2*n], seg[2*n+1]);
            n /= 2;
        }
    }
};
SegTree tree[200005];
int ord[200005];
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, M;
    cin >> N >> M;
    int i, j;
    for(i=0;i<N;i++) dis[i] = INF;
    clock_t st = clock();
    for(i=0;i<M;i++) {
        int a, b, r, p;
        a = rand() % N + 1;
        while(true) {
            b = rand() % N + 1;
            if(b != a) break;
        }
        r = rand() % 1000;
        p = rand() % 10;
        cin >> a >> b >> r >> p;
        //cout << a << ' ' << b << ' ' << r << ' ' << p << '\n';
        adj[b-1].push_back({a-1, r, p, ord[a-1]});
        ord[a-1]++;
    }
    for(i=0;i<N;i++) {
        tree[i].init(ord[i]+1);
    }
    for(i=0;i<N;i++) {
        for(auto n2 : adj[i]) {
            tree[n2[0]].Edit(n2[3], n2[1]);
        }
    }
    for(i=0;i<N;i++) {
        dis[i] = tree[i].seg[1];
    }
    priority_queue<array<int, 2>> PQ;
    for(i=0;i<N;i++) PQ.push({dis[i], i});
    while(!PQ.empty()) {
        auto k = PQ.top();
        PQ.pop();
        int id = k[1];
        if(k[0] != dis[id]) continue;
        for(auto n2 : adj[id]) {
            int v = max(n2[1], dis[id] - n2[2]);
            if(v >= 1e12) v = INF;
            tree[n2[0]].Edit(n2[3], v);
            if(dis[n2[0]] != tree[n2[0]].seg[1]) {
                dis[n2[0]] = tree[n2[0]].seg[1];
                PQ.push({dis[n2[0]], n2[0]});
            }
        }
    }
    for(i=0;i<N;i++) {
        cout << (dis[i]>=1e12?-1:dis[i]) << ' ';
    }
    //cout << clock() - st << "ms";
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:36:12: warning: unused variable 'j' [-Wunused-variable]
   36 |     int i, j;
      |            ^
Main.cpp:38:13: warning: unused variable 'st' [-Wunused-variable]
   38 |     clock_t st = clock();
      |             ^~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11732 KB Output is correct
2 Correct 7 ms 11604 KB Output is correct
3 Correct 6 ms 11440 KB Output is correct
4 Correct 7 ms 11604 KB Output is correct
5 Correct 7 ms 11548 KB Output is correct
6 Correct 7 ms 11476 KB Output is correct
7 Correct 6 ms 11476 KB Output is correct
8 Correct 7 ms 11604 KB Output is correct
9 Correct 7 ms 11604 KB Output is correct
10 Correct 6 ms 11476 KB Output is correct
11 Correct 8 ms 11504 KB Output is correct
12 Correct 6 ms 11464 KB Output is correct
13 Correct 6 ms 11312 KB Output is correct
14 Correct 8 ms 11604 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 37564 KB Output is correct
2 Correct 296 ms 37548 KB Output is correct
3 Correct 91 ms 25236 KB Output is correct
4 Correct 63 ms 25648 KB Output is correct
5 Correct 195 ms 31480 KB Output is correct
6 Correct 213 ms 31588 KB Output is correct
7 Correct 96 ms 23736 KB Output is correct
8 Correct 294 ms 38552 KB Output is correct
9 Correct 295 ms 42216 KB Output is correct
10 Correct 82 ms 25904 KB Output is correct
11 Correct 221 ms 34672 KB Output is correct
12 Correct 79 ms 24972 KB Output is correct
13 Correct 85 ms 23184 KB Output is correct
14 Correct 311 ms 43224 KB Output is correct
15 Correct 311 ms 43276 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11732 KB Output is correct
2 Correct 7 ms 11604 KB Output is correct
3 Correct 6 ms 11440 KB Output is correct
4 Correct 7 ms 11604 KB Output is correct
5 Correct 7 ms 11548 KB Output is correct
6 Correct 7 ms 11476 KB Output is correct
7 Correct 6 ms 11476 KB Output is correct
8 Correct 7 ms 11604 KB Output is correct
9 Correct 7 ms 11604 KB Output is correct
10 Correct 6 ms 11476 KB Output is correct
11 Correct 8 ms 11504 KB Output is correct
12 Correct 6 ms 11464 KB Output is correct
13 Correct 6 ms 11312 KB Output is correct
14 Correct 8 ms 11604 KB Output is correct
15 Correct 305 ms 37564 KB Output is correct
16 Correct 296 ms 37548 KB Output is correct
17 Correct 91 ms 25236 KB Output is correct
18 Correct 63 ms 25648 KB Output is correct
19 Correct 195 ms 31480 KB Output is correct
20 Correct 213 ms 31588 KB Output is correct
21 Correct 96 ms 23736 KB Output is correct
22 Correct 294 ms 38552 KB Output is correct
23 Correct 295 ms 42216 KB Output is correct
24 Correct 82 ms 25904 KB Output is correct
25 Correct 221 ms 34672 KB Output is correct
26 Correct 79 ms 24972 KB Output is correct
27 Correct 85 ms 23184 KB Output is correct
28 Correct 311 ms 43224 KB Output is correct
29 Correct 311 ms 43276 KB Output is correct
30 Correct 333 ms 42304 KB Output is correct
31 Correct 322 ms 42280 KB Output is correct
32 Correct 82 ms 27188 KB Output is correct
33 Correct 64 ms 25776 KB Output is correct
34 Correct 234 ms 36024 KB Output is correct
35 Correct 236 ms 36224 KB Output is correct
36 Correct 112 ms 27436 KB Output is correct
37 Correct 315 ms 43240 KB Output is correct
38 Correct 305 ms 43196 KB Output is correct
39 Correct 90 ms 25928 KB Output is correct
40 Correct 234 ms 34552 KB Output is correct
41 Correct 80 ms 24928 KB Output is correct
42 Correct 91 ms 23232 KB Output is correct
43 Correct 335 ms 43240 KB Output is correct
44 Correct 330 ms 43236 KB Output is correct
45 Correct 319 ms 43308 KB Output is correct
46 Correct 212 ms 33384 KB Output is correct
47 Correct 229 ms 33468 KB Output is correct
48 Correct 185 ms 35572 KB Output is correct
49 Correct 263 ms 35376 KB Output is correct
50 Correct 6 ms 11220 KB Output is correct