Submission #334655

#	Time	Username	Problem	Language	Result	Execution time	Memory
334655		ijxjdjd	Crocodile's Underground City (IOI11_crocodile)	C++11	100 / 100	635 ms	61668 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;

typedef long long ll;
typedef string str;
typedef double db;
typedef long double ld;

typedef pair<int, int> pi;
typedef  pair<long, long> pl;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;


#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define FR(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define RF(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MAXN = (int)(1e5)+5;
const int INF = (int)(1e9) + 5;
int from[MAXN];
int dist[MAXN];
int dist2[MAXN];
vector<pair<int, int>> adj[MAXN];
void dijkstra(int K, int P[]) {
    FR(i, MAXN) {
        dist[i] = INF;
        from[i] = 0;
        dist2[i] = INF;
    }
    priority_queue<pi,vector<pair<int,int>>,greater<pair<int,int>>> q;
    FR(i, K) {
        from[P[i]] = 1;
        dist[P[i]] = 0;
        dist2[P[i]] = 0;
        q.push({0,P[i]});
    }
    while(!q.empty())
    {
        pair<int,int> p = q.top();
        q.pop();
        int u = p.second, d = p.first;
        if (from[u] == 0) {
            from[u]++;
            continue;
        }
        else if (from[u] == 1) {
            from[u]++;
            for(pi pr : adj[u]) {
                int v = pr.second;
                int next_dist = d + pr.first;
                if(next_dist < dist[v])
                {
                    dist2[v] = dist[v];
                    dist[v] = next_dist;
                    q.push({next_dist,v});
                }
                else if (next_dist < dist2[v]) {
                    dist2[v] = next_dist;
                    q.push({next_dist,v});
                }
            }

        }
    }
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    for (int i = 0; i < M; i++) {
        adj[R[i][1]].push_back({L[i], R[i][0]});
        adj[R[i][0]].push_back({L[i], R[i][1]});
    }
    dijkstra(K, P);
    return dist2[0];
}

• Subtask 1: 46 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11