oj.uz

Submission #525613

# Submission time Handle Problem Language Result Execution time Memory
525613 2022-02-12T06:43:56 Z aadit_ambadkar Ferries (NOI13_ferries) C++17
0 / 40
 299 ms 27892 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 INF 1000000000000000007LL
#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, INF);
multiset<ll, greater<int>> ts;

ll dfs(int node) {
    if (vis[node]==1) return INF;
    else if (vis[node]==2) return mn[node];
    if (node==n-1) {
        vis[node]=2;
        mn[node]=0;
        return 0;
    }
    vis[node]=1;
    ts.clear();
    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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8524 KB Output is correct
2 Incorrect 5 ms 8524 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 10352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 299 ms 27892 KB Output isn't correct
2 Halted 0 ms 0 KB -