oj.uz

Submission #525614

# Submission time Handle Problem Language Result Execution time Memory
525614 2022-02-12T06:44:25 Z aadit_ambadkar Ferries (NOI13_ferries) C++11
28 / 40
 277 ms 29760 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);

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;
    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 4 ms 8524 KB Output is correct
2 Correct 5 ms 8684 KB Output is correct
3 Correct 15 ms 10236 KB Output is correct
4 Correct 158 ms 26132 KB Output is correct
5 Correct 154 ms 26036 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8524 KB Output is correct
2 Correct 5 ms 8652 KB Output is correct
3 Correct 13 ms 10060 KB Output is correct
4 Correct 60 ms 17316 KB Output is correct
5 Correct 93 ms 17736 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 10444 KB Output is correct
2 Correct 25 ms 10384 KB Output is correct
3 Correct 277 ms 28168 KB Output is correct
4 Correct 264 ms 26052 KB Output is correct
5 Correct 258 ms 25996 KB Output is correct

Subtask #4
0 / 12.0

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