제출 #842079

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
842079		TS_2392	악어의 지하 도시 (IOI11_crocodile)	C++14	100 / 100	378 ms	76116 KiB

crocodile

#include <bits/stdc++.h>
#include "crocodile.h"
 
using namespace std;
 
#define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define SPEED        ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define EL           cout << '\n'
#define dbg(x)       cout << #x << " = " << (x) << ' '
#define dbgp(x)      cout << #x << " = (" << (x.fi) << ", " << (x.se) << ") "
 
#define epl          emplace
#define pb           push_back
#define eb           emplace_back
#define fi           first
#define se           second
#define mp           make_pair
 
#define sqr(x)       ((x) * (x))
#define all(x)       (x).begin(), (x).end()
#define rall(x)      (x).rbegin(), (x).rend()
#define lwb          lower_bound
#define upb          upper_bound
#define ctz          __builtin_ctzll
#define pct          __builtin_popcountll
 
typedef long long            ll;
typedef long double          ldb;
typedef unsigned int         uint;
typedef unsigned long long   ull;
typedef pair<ll, ll>         pll;
typedef pair<ll, int>        pli;
typedef pair<int, ll>        pil;
typedef pair<int, int>       pii;
typedef pair<ldb, ldb>       pld;
typedef pair<double, double> pdd;
 
template<class T1, class T2> bool minimize(T1 &a, T2 b){return a > b ? a = b, true : false;}
template<class T1, class T2> bool maximize(T1 &a, T2 b){return a < b ? a = b, true : false;}
 
int d4x[4] = {1, 0, -1, 0}, d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int d4y[4] = {0, 1, 0, -1}, d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
//-----------------------------------------------------------------------//
const int N = 1e5 + 3, M = 1e6 + 3;
const ll oo = 1e17;
int n, m, k;// R[M][2], L[M], P[N];
vector<pii> adj[N];
pll d[N];
struct state{
    int vertex; pll di;
    bool operator < (const state &oth) const{
        return di.se > oth.di.se;
    }
};
priority_queue<state> pq;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
    n = N, m = M, k = K;
    for(int i = 0; i < m; ++i){
        adj[R[i][0]].eb(R[i][1], L[i]);
        adj[R[i][1]].eb(R[i][0], L[i]);
    }
    for(int i = 0; i < n; ++i) d[i] = {oo, oo};
    for(int i = 0; i < k; ++i){
        d[P[i]] = {0, 0};
        pq.push({P[i], d[P[i]]});
    }
    while(!pq.empty()){
        int u = pq.top().vertex;
        pll dist = pq.top().di;
        pq.pop();
        if(dist != d[u]) continue;
        if(d[u].se == oo) break;
        for(int i = 0; i < adj[u].size(); ++i){
            int v = adj[u][i].fi;
            ll w = adj[u][i].se;
            if(d[v].fi > d[u].se + w){
                d[v].se = d[v].fi;
                d[v].fi = d[u].se + w;
                pq.push({v, d[v]});
            }
            else if(minimize(d[v].se, d[u].se + w)){
                pq.push({v, d[v]});
            }
        }
    }
    return d[0].se;
}

컴파일 시 표준 에러 (stderr) 메시지

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:73:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for(int i = 0; i < adj[u].size(); ++i){
      |                        ~~^~~~~~~~~~~~~~~

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