Submission #1109659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109659		thangdz2k7	Travelling Merchant (CCO21_day2problem1)	C++17	25 / 25	173 ms	23480 KiB

Main

// author : thembululquaUwU
// 3.9.2024

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define endl '\n'

using namespace std;
using ll = long long;
using ii = pair <int, int>;
using vi = vector <int>;

const int N = 2e5 + 5;
const int mod = 1e9 + 7;

void maxl(auto &a, auto b) {a = max(a, b);}
void minl(auto &a, auto b) {a = min(a, b);}

struct Edge{
    int u, v, r, p;
};

void solve(){
    int n, m;
    cin >> n >> m;
    vector <Edge> e(m); m = 0;
    vector <vector <int>> radj(n);
    vector <int> deg(n);
    for (auto &[u, v, r, p] : e) {
        cin >> u >> v >> r >> p;
        -- u, -- v;
        radj[v].push_back(m ++);
        deg[u] ++;
    }

    vector <int> ans(n, -1), used(m, 0);
    queue <int> qu;
    for (int u = 0; u < n; ++ u){
        if (!deg[u]) qu.push(u);
    }
    while (qu.size()){
        int u = qu.front(); qu.pop();
        for (int id : radj[u]){
            used[id] = 1;
            if (!--deg[e[id].u]) qu.push(e[id].u);
        }
    }

    priority_queue <pair <int, int>> pq;
    for (int id = 0; id < m; ++ id){
        if (!used[id]) pq.push({e[id].r, id});
    }
    while (pq.size()){
        auto [ru, id] = pq.top(); pq.pop();
        if (used[id]) continue;
        used[id] = 1;
        int u = e[id].u;
        if (!--deg[u]){
            assert(deg[u] >= 0);
            ans[u] = ru;
            for (int id : radj[u]) if (e[id].r < ru - e[id].p) {
                int v = e[id].u;
                pq.push({ru - e[id].p, id});
            }
        }
    }

    for (int i = 0; i < n; ++ i) cout << ans[i] << ' ';
}

int main(){
    if (fopen("pqh.inp", "r")){
        freopen("pqh.inp", "r", stdin);
        freopen("pqh.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int t = 1; // cin >> t;
    while (t --) solve();
    return 0;
}

Compilation message (stderr)

Main.cpp:18:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | void maxl(auto &a, auto b) {a = max(a, b);}
      |           ^~~~
Main.cpp:18:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   18 | void maxl(auto &a, auto b) {a = max(a, b);}
      |                    ^~~~
Main.cpp:19:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void minl(auto &a, auto b) {a = min(a, b);}
      |           ^~~~
Main.cpp:19:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | void minl(auto &a, auto b) {a = min(a, b);}
      |                    ^~~~
Main.cpp: In function 'void solve()':
Main.cpp:64:21: warning: unused variable 'v' [-Wunused-variable]
   64 |                 int v = e[id].u;
      |                     ^
Main.cpp: In function 'int main()':
Main.cpp:75:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         freopen("pqh.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:76:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         freopen("pqh.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16