oj.uz

Submission #778893

# Submission time Handle Problem Language Result Execution time Memory
778893 2023-07-11T01:03:12 Z mrwang Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 402 ms 65676 KB 
#include "crocodile.h"
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e9+10;
const ll mod=1e9+7;
pli merg(pli a,int b)
{
    pli ans;
    int x[3];
    x[0]=a.fi;
    x[1]=a.se;
    x[2]=b;
    sort(x,x+3);
    ans.fi=x[0];
    ans.se=x[1];
    return ans;
}
vector<pli>g[maxN];
pli dis[maxN];
bool vis[maxN];
#define pll pair<pli,int>
priority_queue<pli,vector<pli>,greater<pli>>pq;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    for(int i=0;i<M;i++)
    {
        g[R[i][1]].pb({R[i][0],L[i]});
        g[R[i][0]].pb({R[i][1],L[i]});
    }
    for(int i=0;i<N;i++)
    {
        dis[i]={inf,inf};
        vis[i]=false;
    }
    for(int i=0;i<K;i++)
    {
        //dis[P[i]]={0,inf};
        pq.push({0,P[i]});

    }
    while(!pq.empty())
    {
        ll u=pq.top().se;
        ll d=pq.top().fi;
        pq.pop();
        if(vis[u]==true) continue;
        vis[u]=true;
        for(auto zz:g[u])
        {
            int v=zz.fi;
            int w=zz.se;
            pli cc;
            cc=merg(dis[v],w+d);
            //cout << v<<' '<<u<<' '<<w+d<<'\n';
            if(dis[v]!=cc)
            {
                dis[v]=cc;
                //cout << v<<' '<<cc.se<<'\n';
                pq.push({dis[v].se,v});
            }
        }
    }
    return dis[0].se;
}
/*signed main()
{
  int ans;
  read_input();
  ans = travel_plan(N,M,R,L,K,P);
  if(ans==solution)
    printf("Correct.\n");
  else
    printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);

  return 0;
}
*/

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 3 ms 5028 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5024 KB Output is correct
7 Correct 4 ms 5028 KB Output is correct
8 Correct 4 ms 5076 KB Output is correct
9 Correct 5 ms 5204 KB Output is correct
10 Correct 3 ms 5008 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 6 ms 5436 KB Output is correct
13 Correct 6 ms 5540 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 4 ms 5072 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 4948 KB Output is correct
4 Correct 3 ms 5028 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5024 KB Output is correct
7 Correct 4 ms 5028 KB Output is correct
8 Correct 4 ms 5076 KB Output is correct
9 Correct 5 ms 5204 KB Output is correct
10 Correct 3 ms 5008 KB Output is correct
11 Correct 3 ms 5076 KB Output is correct
12 Correct 6 ms 5436 KB Output is correct
13 Correct 6 ms 5540 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 4 ms 5072 KB Output is correct
16 Correct 326 ms 60616 KB Output is correct
17 Correct 83 ms 17352 KB Output is correct
18 Correct 85 ms 18780 KB Output is correct
19 Correct 402 ms 65676 KB Output is correct
20 Correct 252 ms 51724 KB Output is correct
21 Correct 42 ms 10396 KB Output is correct
22 Correct 277 ms 48604 KB Output is correct