oj.uz

Submission #1102431

# Submission time Handle Problem Language Result Execution time Memory
1102431 2024-10-18T06:23:41 Z vjudge1 Travelling Merchant (CCO21_day2problem1) C++17
25 / 25
 239 ms 53388 KB 
/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define int long long
#define isz(x) (int)x.size()
using namespace std;

template<class T>
struct graph{
    using Weight_t = T;
    struct Edge_t{
        int from, to;
        T cost;
    };
    int n;
    vector<Edge_t> edge;
    vector<vector<int>> adj;
    function<bool(int)> ignore;
    graph(int n = 1): n(n), adj(n){
        assert(n >= 1);
    }
    graph(const vector<vector<int>> &adj, bool undirected = true): n((int)adj.size()), adj(n){
        assert(n >= 1);
        if(undirected){
            for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) if(u < v) link(u, v);
        }
        else for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) orient(u, v);
    }
    graph(const vector<vector<pair<int, T>>> &adj, bool undirected = true): n((int)adj.size()), adj(n){
        assert(n >= 1);
        if(undirected){
            for(auto u = 0; u < n; ++ u) for(auto [v, w]: adj[u]) if(u < v) link(u, v, w);
        }
        else for(auto u = 0; u < n; ++ u) for(auto [v, w]: adj[u]) orient(u, v, w);
    }
    graph(int n, vector<array<int, 2>> &edge, bool undirected = true): n(n), adj(n){
        assert(n >= 1);
        for(auto [u, v]: edge) undirected ? link(u, v) : orient(u, v);
    }
    graph(int n, vector<tuple<int, int, T>> &edge, bool undirected = true): n(n), adj(n){
        assert(n >= 1);
        for(auto [u, v, w]: edge) undirected ? link(u, v, w) : orient(u, v, w);
    }
    int add_vertex(){
        adj.emplace_back();
        return n ++;
    }
    int operator()(int u, int id) const{
        #ifdef LOCAL
        assert(0 <= id && id < (int)edge.size());
        assert(edge[id].from == u || edge[id].to == u);
        #endif
        return u ^ edge[id].from ^ edge[id].to;
    }
    int link(int u, int v, T w = {}){ // insert an undirected edge
        int id = (int)edge.size();
        adj[u].push_back(id), adj[v].push_back(id), edge.push_back({u, v, w});
        return id;
    }
    int orient(int u, int v, T w = {}){ // insert a directed edge
        int id = (int)edge.size();
        adj[u].push_back(id), edge.push_back({u, v, w});
        return id;
    }
    vector<int> neighbor(int u, int exclude = -1) const{
        vector<int> res;
        for(auto id: adj[u]){
            if(id == exclude || ignore && ignore(id)) continue;
            res.push_back(operator()(u, id));
        }
        return res;
    }
    void clear(){
        for(auto [u, v, w]: edge){
            adj[u].clear();
            adj[v].clear();
        }
        edge.clear();
        ignore = {};
    }
    graph transpose() const{ // the transpose of the directed graph
        graph res(n);
        for(auto id = 0; id < (int)edge.size(); ++ id){
            if(ignore && ignore(id)) continue;
            res.orient(edge[id].to, edge[id].from, edge[id].cost);
        }
        return res;
    }
    int degree(int u) const{ // the degree (outdegree if directed) of u (without the ignoration rule)
        return (int)adj[u].size();
    }
    // The adjacency list is sorted for each vertex.
    vector<vector<int>> get_adjacency_list() const{
        vector<vector<int>> res(n);
        for(auto u = 0; u < n; ++ u) for(auto id: adj[u]){
            if(ignore && ignore(id)) continue;
            res[(*this)(u, id)].push_back(u);
        }
        return res;
    }
    void set_ignoration_rule(const function<bool(int)> &f){
        ignore = f;
    }
    void reset_ignoration_rule(){
        ignore = nullptr;
    }
    friend ostream &operator<<(ostream &out, const graph &g){
        for(auto id = 0; id < (int)g.edge.size(); ++ id){
            if(g.ignore && g.ignore(id)) continue;
            auto &e = g.edge[id];
            out << "{" << e.from << ", " << e.to << ", " << e.cost << "}\n";
        }
        return out;
    }
};

const int inf = 1e18;
const int lim = 1e10;

void solve() {
    int n, m;
    cin >> n >> m;

    vector<int> outdeg(n);
    graph<pair<int, int>> g(n), rg(n);
    for (int i = 0; i < m; ++i) {
        int u, v, r, p;
        cin >> u >> v >> r >> p;
        --u, --v;
        g.orient(u, v, {r, p});
        rg.orient(v, u, {r, p});
        ++outdeg[u];
    }

    vector<int> vec;
    vector<int> vis_edge(m);
    for (int i = 0; i < n; ++i) {
        if (outdeg[i] == 0) {
            vec.emplace_back(i);
        }
    }
    while (not vec.empty()) {
        int u = vec.back();
        vec.pop_back();
        for (auto id : rg.adj[u]) {
            auto v = rg(u, id);
            vis_edge[id] = true;
            if (--outdeg[v] == 0) {
                vec.emplace_back(v);
            }
        }
    }

    vector<int> needed(n, -1);
    priority_queue<pair<int, int>> pq;
    for (int i = 0; i < m; ++i) if (not vis_edge[i]) {
        pq.emplace(g.edge[i].cost.first, i);
    }
    while (not pq.empty()) {
        auto [r, id] = pq.top();
        pq.pop();
        if (vis_edge[id]) {
            continue;
        }
        vis_edge[id] = true;
        auto u = g.edge[id].from;
        needed[u] = r;
        if (--outdeg[u] == 0) {
            for (auto id : rg.adj[u]) {
                pq.emplace(needed[u] - g.edge[id].cost.second, id);
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        cout << needed[i] << " \n"[i + 1 == n];
    } 

}

signed main() {

#ifndef CDuongg
    if (fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
   // auto end = chrono::high_resolution_clock::now();
   // cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
   // cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif

}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 848 KB Output is correct
2 Correct 2 ms 804 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 848 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 3 ms 592 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 2 ms 848 KB Output is correct
9 Correct 2 ms 848 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 2 ms 592 KB Output is correct
12 Correct 1 ms 592 KB Output is correct
13 Correct 1 ms 592 KB Output is correct
14 Correct 2 ms 848 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 41612 KB Output is correct
2 Correct 145 ms 41604 KB Output is correct
3 Correct 93 ms 31016 KB Output is correct
4 Correct 21 ms 16848 KB Output is correct
5 Correct 194 ms 40584 KB Output is correct
6 Correct 167 ms 40332 KB Output is correct
7 Correct 102 ms 30164 KB Output is correct
8 Correct 210 ms 52624 KB Output is correct
9 Correct 237 ms 51332 KB Output is correct
10 Correct 96 ms 29992 KB Output is correct
11 Correct 188 ms 39556 KB Output is correct
12 Correct 82 ms 30452 KB Output is correct
13 Correct 82 ms 29916 KB Output is correct
14 Correct 192 ms 52620 KB Output is correct
15 Correct 199 ms 52688 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 848 KB Output is correct
2 Correct 2 ms 804 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 848 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 3 ms 592 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 2 ms 848 KB Output is correct
9 Correct 2 ms 848 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 2 ms 592 KB Output is correct
12 Correct 1 ms 592 KB Output is correct
13 Correct 1 ms 592 KB Output is correct
14 Correct 2 ms 848 KB Output is correct
15 Correct 127 ms 41612 KB Output is correct
16 Correct 145 ms 41604 KB Output is correct
17 Correct 93 ms 31016 KB Output is correct
18 Correct 21 ms 16848 KB Output is correct
19 Correct 194 ms 40584 KB Output is correct
20 Correct 167 ms 40332 KB Output is correct
21 Correct 102 ms 30164 KB Output is correct
22 Correct 210 ms 52624 KB Output is correct
23 Correct 237 ms 51332 KB Output is correct
24 Correct 96 ms 29992 KB Output is correct
25 Correct 188 ms 39556 KB Output is correct
26 Correct 82 ms 30452 KB Output is correct
27 Correct 82 ms 29916 KB Output is correct
28 Correct 192 ms 52620 KB Output is correct
29 Correct 199 ms 52688 KB Output is correct
30 Correct 152 ms 41600 KB Output is correct
31 Correct 156 ms 41400 KB Output is correct
32 Correct 108 ms 31788 KB Output is correct
33 Correct 22 ms 16844 KB Output is correct
34 Correct 154 ms 40328 KB Output is correct
35 Correct 163 ms 40324 KB Output is correct
36 Correct 113 ms 30176 KB Output is correct
37 Correct 237 ms 52876 KB Output is correct
38 Correct 239 ms 50572 KB Output is correct
39 Correct 100 ms 29988 KB Output is correct
40 Correct 157 ms 40136 KB Output is correct
41 Correct 96 ms 30188 KB Output is correct
42 Correct 83 ms 30172 KB Output is correct
43 Correct 237 ms 53384 KB Output is correct
44 Correct 232 ms 53388 KB Output is correct
45 Correct 196 ms 52620 KB Output is correct
46 Correct 132 ms 37572 KB Output is correct
47 Correct 126 ms 40320 KB Output is correct
48 Correct 148 ms 40808 KB Output is correct
49 Correct 154 ms 39812 KB Output is correct
50 Correct 1 ms 336 KB Output is correct