제출 #1025460

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1025460		mindiyak	경주 (Race) (IOI11_race)	C++14	9 / 100	165 ms	262144 KiB

race

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
#include <string>
#include <iostream>
#include <cmath>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i, a, b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i, a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto &a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define len(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define nl endl
#define S second
#define lb lower_bound
#define ub upper_bound
#define aint(x) x.begin(), x.end()
#define raint(x) x.rbegin(), x.rend()
#define ins insert
const int MOD = 1000000007;
#include "race.h"

/*
1.BFS numer of children (priority queue with visited)
2.Check children nodes with each other (set with upper and lower bound)
3.Save children distances to the parent node (save a set with distances to each leaf)
 */

// vector<vpi> paths(2e5+3,vpi());
// vector<vector<vpi>> dist(2e5+3,vector<vpi>(102,vpi()));
// // vpi dist[200003][102];
// vi children(2e5+3);
// vi parent(2e5+3,-1);
// vi parent_dist(2e5+3,-1);

vector<vpi> paths;
vector<vector<vpi>> dist;
// vpi dist[200003][102];
vi children;
vi parent;
vi parent_dist;

void dfs(int pos,int prev){
  int sum = 1;
  for(auto node:paths[pos]){
    if(node.F == prev)continue;
    parent[node.F] = pos;
    parent_dist[node.F] = node.S;
    dfs(node.F,pos);
    sum += children[node.F];
  }
  children[pos] = sum;
}

int best_path(int N, int K, int H[][2], int L[])
{
  paths = vector<vpi>(N,vpi());
  dist = vector<vector<vpi>> (N,vector<vpi>(103,vpi(2,{1e9,-1})));
  // vpi dist[200003][102];
  children = vi (N);
  parent = vi (N,-1);
  parent_dist = vi (N,-1);

  FOR(i,0,N-1){
    paths[H[i][0]].pb({H[i][1],L[i]});
    paths[H[i][1]].pb({H[i][0],L[i]});
  }

  dfs(0,-1);

  // FOR(i,0,N)cout << children[i] << " ";
  // cout << endl;
  // FOR(i,0,N)cout << parent[i] << " ";
  // cout << endl;
  // FOR(i,0,N)cout << parent_dist[i] << " ";
  // cout << endl;

  priority_queue<pi> pq;
  FOR(i,0,N){
    pq.push({-children[i],i});
  }

  int ans = 1e9;

  while(!pq.empty()){
    int node = pq.top().S;pq.pop();
    // cout << node << " | " << endl;
    FOR(j,0,55){
      if(dist[node][j][0].F != 1e9){
        pi a = dist[node][j][0];
        FOR(l,0,2){
          if(dist[node][K-j][l].F != 1e9){
            if(dist[node][K-j][l].S != a.S){
              ans = min(ans,a.F+dist[node][K-j][l].F+1);
            }
          }
        }
      }
    }

    if(parent[node] == -1)continue;
    
    // cout << "b " << endl;
    if(parent_dist[node] == K){
      // cout << "2 ans - " << 2 << endl;
      ans = min(ans, 2);
    }
    if(parent_dist[node] <= K){
      if(dist[parent[node]][parent_dist[node]][0].F > 1){
        swap(dist[parent[node]][parent_dist[node]][0],dist[parent[node]][parent_dist[node]][1]);
        dist[parent[node]][parent_dist[node]][0] = {1,node};
      }else if(dist[parent[node]][parent_dist[node]][1].F > 1){
        dist[parent[node]][parent_dist[node]][1] = {1,node};
      }
    }
    // cout << "c" << endl;
    FOR(j,0,103){
      if(dist[node][j][0].F != 1e9){
        pi a = dist[node][j][0];
        if(parent_dist[node]+j == K){
          ans = min(ans, a.F+2);
        }
        if(parent_dist[node]+j >= K)continue;
        if(dist[parent[node]][parent_dist[node]+j][0].F > a.F+1){
          swap(dist[parent[node]][parent_dist[node]+j][0],dist[parent[node]][parent_dist[node]+j][1]);
          dist[parent[node]][parent_dist[node]+j][0] = {a.F+1,node};
        }
        else if(dist[parent[node]][parent_dist[node]+j][1].F > a.F+1){
          dist[parent[node]][parent_dist[node]+j][1] = {a.F+1,node};
        }
        // cout << "d" << endl;
      }
      // cout << "e" << endl;

      // FOR(k,0,dist[node][j].size()){
      //   pi a = dist[node][j][k];
      //   // cout << "c " << parent[node] << " " << parent_dist[node]+a.F << " " << a.S.F+1 << " " << node  << endl;
      //   if(parent_dist[node]+j == K){
      //     // cout << " 2 ans - " << a.S.F+2 << endl;
      //     ans = min(ans, a.F+2);
      //   }
      //   if(parent_dist[node]+j >= K)continue;
      //   dist[parent[node]][parent_dist[node]+j].pb({a.F+1,node});
      // }
    }
    // cout << endl;
  }

  if(ans == 1e9)return -1;
  return ans-1;
}

• Subtask 1: 9 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57