oj.uz

Submission #989306

# Submission time Handle Problem Language Result Execution time Memory
989306 2024-05-28T00:34:47 Z sondos225 Crocodile's Underground City (IOI11_crocodile) C++17
46 / 100
 3 ms 9052 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "grader.cpp"
#endif // LOCAL
#define forr(x,i,n) for(int x=i; x<n; x++)
#define pb push_back
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define sz size()
bool vis[100000];
bool ex[100000];
//int routes[100000];
vector<pii> a[100000];
vector<int> dp[100000];
int dfs(int x)
{
    //cout<<x<<endl;
    if (ex[x])
    {
        return 0;
    }
   // if (routes[x]!=0) return routes[x];
        int ch1=INT_MAX, ch2=INT_MAX;
        forr(i,0,a[x].sz)
        {
            auto y=a[x][i];
            if (dp[x][i]==0){
            if (!vis[y.fi])
            {
                vis[y.fi]=1;

                int ch=(dfs(y.fi))+y.se;// cout<<x<<' '<<y.fi<<' '<<ch<<endl;
                dp[x][i]=ch;
                if (ch<=ch1 && ch<=ch2)
                {
                    ch2=ch1;
                    ch1=ch;
                }
                else if (ch>=ch1 && ch<=ch2)
                {
                    ch2=ch;
                }
                vis[y.fi]=0;
            }
            }
            else
            {
                int ch=dp[x][i];
                if (ch<=ch1 && ch<=ch2)
                {
                    ch2=ch1;
                    ch1=ch;
                }
                else if (ch>=ch1 && ch<=ch2)
                {
                    ch2=ch;
                }
            }
        }
        //sort(all(ch));
        if (ch2==INT_MAX) return ch1;
        return ch2;
        // routes[x]=
      //  ch2;
}
int travel_plan(int n, int m, int r[][2], int l[], int k, int e[])
{
    //r/l/k/e/
    forr(i,0,m)
    {
        int x=r[i][0];
        int y=r[i][1];
        a[x].pb({y,l[i]});
        a[y].pb({x,l[i]});
        dp[x].pb(0);
        dp[y].pb(0);
    }

    forr(i,0,k) ex[e[i]]=1;
vis[0]=1;
  return dfs(0);
}

Compilation message

crocodile.cpp: In function 'int dfs(int)':
crocodile.cpp:7:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define forr(x,i,n) for(int x=i; x<n; x++)
      |                                   ^
crocodile.cpp:28:9: note: in expansion of macro 'forr'
   28 |         forr(i,0,a[x].sz)
      |         ^~~~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 1 ms 8796 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 1 ms 8796 KB Output is correct
9 Correct 3 ms 9052 KB Output is correct
10 Incorrect 1 ms 8796 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 1 ms 8796 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 1 ms 8796 KB Output is correct
9 Correct 3 ms 9052 KB Output is correct
10 Incorrect 1 ms 8796 KB Output isn't correct
11 Halted 0 ms 0 KB -