Submission #393793

#	Time	Username	Problem	Language	Result	Execution time	Memory
393793		L_lawliet27	Crocodile's Underground City (IOI11_crocodile)	C++17	100 / 100	635 ms	56068 KiB

crocodile

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#define pb push_back
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define f first
#define s second
#define sz(x) (ll)(x.size())
using namespace std;
using namespace __gnu_pbds;
 
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int getRand(int l, int r)
{
    uniform_int_distribution<int> uid(l, r);
    return uid(rng);
}

const int mod = 1e9+7;

int expo_pow(int x,int y){
 if(y == 0) return 1;
  y=y%(mod-1);
  x%=mod;
  if(y==0) y=mod-1;
  int res=1;
  while(y){
    if(y&1) res=(res*x)%mod;
    x=(x*x)%mod;
    y>>=1; 
  }
  return res;
}

ll add()
{
    return 0;
}

template <typename T, typename... Types>
T add(T var1, Types... var2){
    return (((((ll)(var1)) % mod + (ll)(add(var2...))) % mod) + mod) % mod;
}

ll mul(){
    return 1;
}

template <typename T, typename... Types>
T mul(T var1, Types... var2){
    return (((ll)(var1)) % mod * (ll)(mul(var2...))) % mod;
}

const ll inf = 1e18;

int travel_plan(int n,int m,int r[][2],int l[],int k,int p[]){
  vector<pii> adj[n];
  for (int i = 0; i < m; ++i) {
    int x = r[i][0];
    int y = r[i][1];
    adj[x].pb({y,l[i]});
    adj[y].pb({x,l[i]});
  }

  priority_queue<pii,vector<pii>,greater<pii>> pq;

  vector<int> cnt(n,0);
  vector<int> visited(n,0);
  vector<ll> dis(n,inf);
  vector<ll> dis2(n,inf);

  for (int i = 0; i < k; ++i) {
    cnt[p[i]] = 3;
    dis[p[i]] = 0;
    dis2[p[i]] = 0;
    pq.push({0,p[i]});
  }

  while (!pq.empty()) {
    auto cur = pq.top();
    pq.pop();
    if (visited[cur.s]) continue;
    visited[cur.s] = 1;
    for (auto u:adj[cur.s]) {
      ll new_dis = cur.f + u.s;
      if (new_dis < dis2[u.f]){ 
        dis[u.f] = dis2[u.f];
        dis2[u.f] = new_dis;
        if (dis[u.f] < inf) pq.push({dis[u.f],u.f});
      }
      else if (new_dis < dis[u.f]) {
        dis[u.f] = new_dis;
        if (dis[u.f] < inf) pq.push({dis[u.f],u.f});
      } 
    }
  }
  return (int)dis[0];
}

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