oj.uz

Submission #314486

# Submission time Handle Problem Language Result Execution time Memory
314486 2020-10-20T03:42:39 Z jli12345 Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 877 ms 64236 KB 
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <functional>
#include <cstdio>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <cstring>
#include <string>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <iterator>
#include <ext/pb_ds/assoc_container.hpp>
#include "crocodile.h"
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;

#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, b, a) for (int i = (b); i >= (a); --i)
#define f first
#define s second
#define mp make_pair
#define pb push_back

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const ll MOD = 1e9+7;

ll mod(ll x, ll mod){
    return x >= mod ? x%mod:x;
}

void fio(string s){
    freopen((s+".in").c_str(), "r", stdin);
    freopen((s+".out").c_str(), "w", stdout);
}

int N, M, K;
vector <pii> arr[100100];

priority_queue<int> stor[100100];
int dist[100100];

struct comp{
    bool operator()(const pii &a, const pii &b){
        return a.s > b.s;
    }
};

priority_queue<pii, vector<pii>, comp> pq;

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    FOR(i, 1, M){
        arr[R[i-1][0]].pb(mp(R[i-1][1], L[i-1]));
        arr[R[i-1][1]].pb(mp(R[i-1][0], L[i-1]));
    }
    memset(dist, INF, sizeof(dist));
    FOR(i, 1, K){
        dist[P[i-1]] = 0;
        pq.push(mp(P[i-1], 0));
    }
    while (!pq.empty()){
        int node = pq.top().f;
        int w = pq.top().s;
        pq.pop();
        if (w > dist[node]) continue;
        FOR(i, 0, (int)arr[node].size()-1){
            int nx = arr[node][i].f;
            int nw = arr[node][i].s;
            if ((int)stor[nx].size() < 2){
                stor[nx].push(w+nw);
            } else if (stor[nx].top() > w+nw){
                stor[nx].pop();
                stor[nx].push(w+nw);
            }
            if ((int)stor[nx].size() >= 2 && dist[nx] > stor[nx].top()){
                dist[nx] = stor[nx].top();
                pq.push(mp(nx, dist[nx]));
            }
        }
    }
    return stor[0].top();
}

Compilation message

crocodile.cpp: In function 'void fio(std::string)':
crocodile.cpp:45:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   45 |     freopen((s+".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
crocodile.cpp:46:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   46 |     freopen((s+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6272 KB Output is correct
2 Correct 4 ms 6272 KB Output is correct
3 Correct 5 ms 6272 KB Output is correct
4 Correct 5 ms 6400 KB Output is correct
5 Correct 6 ms 6304 KB Output is correct
6 Correct 5 ms 6272 KB Output is correct
7 Correct 5 ms 6272 KB Output is correct
8 Correct 5 ms 6272 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6272 KB Output is correct
2 Correct 4 ms 6272 KB Output is correct
3 Correct 5 ms 6272 KB Output is correct
4 Correct 5 ms 6400 KB Output is correct
5 Correct 6 ms 6304 KB Output is correct
6 Correct 5 ms 6272 KB Output is correct
7 Correct 5 ms 6272 KB Output is correct
8 Correct 5 ms 6272 KB Output is correct
9 Correct 6 ms 6528 KB Output is correct
10 Correct 4 ms 6272 KB Output is correct
11 Correct 5 ms 6272 KB Output is correct
12 Correct 8 ms 6656 KB Output is correct
13 Correct 8 ms 6784 KB Output is correct
14 Correct 4 ms 6272 KB Output is correct
15 Correct 5 ms 6272 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6272 KB Output is correct
2 Correct 4 ms 6272 KB Output is correct
3 Correct 5 ms 6272 KB Output is correct
4 Correct 5 ms 6400 KB Output is correct
5 Correct 6 ms 6304 KB Output is correct
6 Correct 5 ms 6272 KB Output is correct
7 Correct 5 ms 6272 KB Output is correct
8 Correct 5 ms 6272 KB Output is correct
9 Correct 6 ms 6528 KB Output is correct
10 Correct 4 ms 6272 KB Output is correct
11 Correct 5 ms 6272 KB Output is correct
12 Correct 8 ms 6656 KB Output is correct
13 Correct 8 ms 6784 KB Output is correct
14 Correct 4 ms 6272 KB Output is correct
15 Correct 5 ms 6272 KB Output is correct
16 Correct 623 ms 60440 KB Output is correct
17 Correct 107 ms 19704 KB Output is correct
18 Correct 148 ms 20856 KB Output is correct
19 Correct 877 ms 64236 KB Output is correct
20 Correct 368 ms 53240 KB Output is correct
21 Correct 52 ms 11896 KB Output is correct
22 Correct 399 ms 50168 KB Output is correct