Submission #314486

#	Time	Username	Problem	Language	Result	Execution time	Memory
314486		jli12345	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	877 ms	64236 KiB

crocodile

#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 (stderr)

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 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11