oj.uz

Submission #393779

# Submission time Handle Problem Language Result Execution time Memory
393779 2021-04-24T13:03:24 Z L_lawliet27 Crocodile's Underground City (IOI11_crocodile) C++17
0 / 100
 1 ms 204 KB 
#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);

  for (int i = 0; i < k; ++i) {
    cnt[p[i]] = 3;
    dis[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;
      cnt[u.f]++;
      if (cnt[u.f] == 1) dis[u.f] = new_dis;
      else if (cnt[u.f] == 2) {
        dis[u.f] = min(dis[u.f],new_dis);
        pq.push({dis[u.f],u.f});
      }
      else if (new_dis > dis[u.f]) {
        dis[u.f] = new_dis;
        pq.push({dis[u.f],u.f});
      }
    }
  }
  return (int)dis[0];
}


//signed main(){
//  fast;
//  int test = 1;
//  int i=1;
//  while(test--){
//  }
//}

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 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 204 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 204 KB Output isn't correct
2 Halted 0 ms 0 KB -