oj.uz

Submission #574321

# Submission time Handle Problem Language Result Execution time Memory
574321 2022-06-08T10:23:25 Z TimDee Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 1 ms 212 KB 
#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,vector<int>&isp) {
    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 (isp[v]) continue;
        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<int> is_p(n,0);
    forn(i,K) {
        is_p[P[i]]=1;
    }
    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,is_p);
    //forn(i,n) cout<<val[i]<<' '; cout<<'\n';
    int ans=inf;
    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

crocodile.cpp: In function 'void bfs(std::vector<std::vector<node> >&, std::vector<int>&, 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++)
......
   35 |             forn(i,adj[v].size()) {
      |                  ~~~~~~~~~~~~~~~  
crocodile.cpp:35:13: note: in expansion of macro 'forn'
   35 |             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++)
......
   64 |         forn(j,adj[i].size()) {
      |              ~~~~~~~~~~~~~~~      
crocodile.cpp:64:9: note: in expansion of macro 'forn'
   64 |         forn(j,adj[i].size()) {
      |         ^~~~

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -