Submission #574318

#	Time	Username	Problem	Language	Result	Execution time	Memory
574318		TimDee	Crocodile's Underground City (IOI11_crocodile)	C++14	0 / 100	1 ms	212 KiB

crocodile

#include "crocodile.h"

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

#define forn(i,n) for (int i=0; i<n; i++)
#define pb(x) push_back(x);
#define inf INT_MAX

struct node {
    int v;
    int val;
};

node makenode(int v, int val) {
    //cout<<"make node "<<v<<' '<<val<<'\n';
    node ret;
    ret.v=v;
    ret.val=val;
    return ret;
}

void bfs(vector<vector<node>>&adj,vector<int>&val) {
    queue<node> q;
    //val[0]=1;
    q.push(makenode(0,0));
    while (!q.empty()) {
        node c=q.front();
        int v=c.v, x=c.val;
        //cout<<v<<' '<<x<<'\n';
        q.pop();
        if (val[v]>x) {
            val[v]=x;
            forn(i,adj[v].size()) {
                q.push(makenode(adj[v][i].v,adj[v][i].val+x));
            }
        }
    }
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    int n=N, m=M;
    vector<int> val(n,inf);
    vector<vector<node>> adj(n);
    forn(i,m) {
        int u=R[i][0], v=R[i][1];
        //cout<<"! "<<u<<' '<<v<<' '<<L[i]<<'\n';
        adj[u].pb(makenode(v,L[i]));    
        adj[v].pb(makenode(u,L[i]));
    }
    bfs(adj,val);
    //forn(i,n) cout<<val[i]<<' '; cout<<'\n';
    int ans=inf;
    vector<int> is_p(n,0);
    forn(i,K) {
        is_p[P[i]]=1;
    }
    forn(i,n) {
	if (is_p[i]) continue;
        int cnt=0;
        vector<int> mn;
        forn(j,adj[i].size()) {
            if (is_p[adj[i][j].v]) {
                cnt++;
                mn.pb(val[i]+adj[i][j].val);
            }
        }
        sort(mn.begin(),mn.end());
        if (cnt>=2) ans=min(ans,mn[1]);
    }

    return ans;
}

Compilation message (stderr)

crocodile.cpp: In function 'void bfs(std::vector<std::vector<node> >&, std::vector<int>&)':
crocodile.cpp:6:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define forn(i,n) for (int i=0; i<n; i++)
......
   34 |             forn(i,adj[v].size()) {
      |                  ~~~~~~~~~~~~~~~  
crocodile.cpp:34:13: note: in expansion of macro 'forn'
   34 |             forn(i,adj[v].size()) {
      |             ^~~~
crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:6:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define forn(i,n) for (int i=0; i<n; i++)
......
   63 |         forn(j,adj[i].size()) {
      |              ~~~~~~~~~~~~~~~      
crocodile.cpp:63:9: note: in expansion of macro 'forn'
   63 |         forn(j,adj[i].size()) {
      |         ^~~~

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