Submission #334482

#	Time	Username	Problem	Language	Result	Execution time	Memory
334482		ijxjdjd	Crocodile's Underground City (IOI11_crocodile)	C++11	0 / 100	3 ms	3584 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];
vector<pair<int, int>> adj[MAXN];
void dijkstra(int K, int P[]) {
    FR(i, MAXN) {
        dist[i] = INF;
        from[i] = -1;
    }
    priority_queue<pi> q;
    FR(i, K) {
        dist[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(d > dist[u]) continue;

        for(pi pr : adj[u])
        {
            int v = pr.second;
            int next_dist = d + pr.first;

            if(next_dist < dist[v])
            {
                dist[v] = next_dist;
                from[v] = u;
                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);
    FR(i, MAXN) {
        if (from[i] != -1) {
            for (int j = 0; j < adj[from[i]].size(); j++) {
                if (adj[from[i]][j].second == i) {
                    adj[from[i]].erase(adj[from[i]].begin() + j);
                    break;
                }
            }
            FR(j, adj[i].size()) {
                if (adj[i][j].second == i) {
                    adj[i].erase(adj[i].begin() + j);
                }
            }
        }
    }
    dijkstra(K, P);
    return dist[0];
}

Compilation message (stderr)

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:70:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |             for (int j = 0; j < adj[from[i]].size(); j++) {
      |                             ~~^~~~~~~~~~~~~~~~~~~~~
crocodile.cpp:18:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 | #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
      |                                        ^
crocodile.cpp:19:17: note: in expansion of macro 'FOR'
   19 | #define FR(i,a) FOR(i,0,a)
      |                 ^~~
crocodile.cpp:76:13: note: in expansion of macro 'FR'
   76 |             FR(j, adj[i].size()) {
      |             ^~

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