oj.uz

Submission #1102430

# Submission time Handle Problem Language Result Execution time Memory
1102430 2024-10-18T06:22:00 Z CDuong Travelling Merchant (CCO21_day2problem1) C++17
25 / 25
 230 ms 58312 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 2 ms 848 KB Output is correct
2 Correct 2 ms 804 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 852 KB Output is correct
9 Correct 2 ms 808 KB Output is correct
10 Correct 2 ms 760 KB Output is correct
11 Correct 2 ms 760 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 2 ms 852 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 41620 KB Output is correct
2 Correct 139 ms 41608 KB Output is correct
3 Correct 93 ms 31784 KB Output is correct
4 Correct 23 ms 17120 KB Output is correct
5 Correct 167 ms 45424 KB Output is correct
6 Correct 161 ms 44860 KB Output is correct
7 Correct 109 ms 34020 KB Output is correct
8 Correct 227 ms 58000 KB Output is correct
9 Correct 196 ms 54268 KB Output is correct
10 Correct 95 ms 33640 KB Output is correct
11 Correct 149 ms 43148 KB Output is correct
12 Correct 93 ms 32176 KB Output is correct
13 Correct 81 ms 31732 KB Output is correct
14 Correct 230 ms 57996 KB Output is correct
15 Correct 221 ms 57500 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 848 KB Output is correct
2 Correct 2 ms 804 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 852 KB Output is correct
9 Correct 2 ms 808 KB Output is correct
10 Correct 2 ms 760 KB Output is correct
11 Correct 2 ms 760 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 2 ms 852 KB Output is correct
15 Correct 132 ms 41620 KB Output is correct
16 Correct 139 ms 41608 KB Output is correct
17 Correct 93 ms 31784 KB Output is correct
18 Correct 23 ms 17120 KB Output is correct
19 Correct 167 ms 45424 KB Output is correct
20 Correct 161 ms 44860 KB Output is correct
21 Correct 109 ms 34020 KB Output is correct
22 Correct 227 ms 58000 KB Output is correct
23 Correct 196 ms 54268 KB Output is correct
24 Correct 95 ms 33640 KB Output is correct
25 Correct 149 ms 43148 KB Output is correct
26 Correct 93 ms 32176 KB Output is correct
27 Correct 81 ms 31732 KB Output is correct
28 Correct 230 ms 57996 KB Output is correct
29 Correct 221 ms 57500 KB Output is correct
30 Correct 143 ms 46480 KB Output is correct
31 Correct 133 ms 46448 KB Output is correct
32 Correct 104 ms 34608 KB Output is correct
33 Correct 21 ms 17104 KB Output is correct
34 Correct 195 ms 45196 KB Output is correct
35 Correct 207 ms 45196 KB Output is correct
36 Correct 109 ms 34016 KB Output is correct
37 Correct 210 ms 57488 KB Output is correct
38 Correct 188 ms 55184 KB Output is correct
39 Correct 112 ms 33796 KB Output is correct
40 Correct 189 ms 43340 KB Output is correct
41 Correct 102 ms 31860 KB Output is correct
42 Correct 85 ms 31632 KB Output is correct
43 Correct 198 ms 57484 KB Output is correct
44 Correct 216 ms 58312 KB Output is correct
45 Correct 193 ms 57484 KB Output is correct
46 Correct 138 ms 40436 KB Output is correct
47 Correct 133 ms 43132 KB Output is correct
48 Correct 144 ms 43628 KB Output is correct
49 Correct 144 ms 43400 KB Output is correct
50 Correct 1 ms 340 KB Output is correct