Submission #1109638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109638		thangdz2k7	Travelling Merchant (CCO21_day2problem1)	C++17	0 / 25	80 ms	19536 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);
    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]){
            if (!--deg[e[id].u]) qu.push(e[id].u);
        }
    }

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

    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 'int main()':
Main.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen("pqh.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:72:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         freopen("pqh.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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