oj.uz

Submission #525608

# Submission time Handle Problem Language Result Execution time Memory
525608 2022-02-12T06:40:01 Z aadit_ambadkar Ferries (NOI13_ferries) C++17
17 / 40
 301 ms 34784 KB 
/*
    This code belongs to Aadit Ambadkar
    Date: 2022-02-11 22:17:56
    Problem: fer
*/
#include <bits/stdc++.h>
using namespace::std;

typedef long long ll;
#define F0R(i, n) for (int i = 0; i < n; i++)
#define R0F(i, n) for (int i = n-1; i >= 0; i--)
#define FOR(i, a, n) for (int i = a; i < n; i++)
#define pb push_back
#define fastio ios::sync_with_stdio(0); cin.tie(0)
#define MOD 1000000007
#define FF first
#define SS second

const int MX = 1e5+5;
int n, m; 
vector<int> adj[MX];
multiset<ll> cs[MX];
vector<int> vis(MX, 0);  // three state dfs (white grey black)
vector<ll> mn(MX, MOD);

ll dfs(int node) {
    if (vis[node]==1) return MOD;
    else if (vis[node]==2) return mn[node];
    if (node==n-1) {
        vis[node]=2;
        mn[node]=0;
        return 0;
    }
    vis[node]=1;
    multiset<ll, greater<int>> ts;
    for (auto i : adj[node]) {
        ll j = dfs(i);
        assert(j==mn[i]);
        ts.insert(j);
    }
    
    // for (auto i : adj[node]) {
    //     cout << i << " ";
    // }
    // cout << "\n";
    // if (node == 0) {
    //     for (auto i : ts) {
    //         cout << i << " ";
    //     }
    //     cout << "\n";
    // }

    auto i1 = ts.begin(), i2 = cs[node].begin();
    ll ans = MOD;
    while (i1!=ts.end() && i2 != cs[node].end()) {
        ans = min(ans, (*(i1))+(*(i2)));
        i1++;
        i2++;
    }
    mn[node]=ans;
    // cout << "MN of " << node << " is " << mn[node] << "\n";
    vis[node]=2;
    return ans;
}

int main() {
    fastio;
    cin >> n >> m;
    F0R(i, m) {
        int a, b; ll c; cin >> a >> b >> c; a--; b--;
        adj[a].pb(b);
        cs[a].insert(c);
    }
    cout << dfs(0) << "\n";

    // F0R(i, n) {
    //     cout << mn[i] << " ";
    // }
    // cout << "\n";

}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8548 KB Output is correct
2 Correct 5 ms 8676 KB Output is correct
3 Correct 16 ms 10524 KB Output is correct
4 Correct 160 ms 29112 KB Output is correct
5 Correct 167 ms 29088 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8532 KB Output is correct
2 Correct 5 ms 8556 KB Output is correct
3 Correct 13 ms 10316 KB Output is correct
4 Correct 64 ms 18724 KB Output is correct
5 Correct 96 ms 19584 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 10856 KB Output is correct
2 Correct 18 ms 10876 KB Output is correct
3 Runtime error 296 ms 33004 KB Memory limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 301 ms 34784 KB Memory limit exceeded
2 Halted 0 ms 0 KB -