Submission #778893

#	Time	Username	Problem	Language	Result	Execution time	Memory
778893		mrwang	Crocodile's Underground City (IOI11_crocodile)	C++14	100 / 100	402 ms	65676 KiB

crocodile

#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 / 46
• Subtask 2: 43 / 43
• Subtask 3: 11 / 11