Submission #696357

#	Time	Username	Problem	Language	Result	Execution time	Memory
696357		Cross_Ratio	Travelling Merchant (CCO21_day2problem1)	C++14	25 / 25	335 ms	43308 KiB

Main

#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 (stderr)

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 / 4
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16