| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1127022 | neverspot | 경주 (Race) (IOI11_race) | C++20 | 0 ms | 0 KiB |
/* "If I can run I will run , If I can walk I will walk , If I can crawl I will crawl" */
/* " But I will NEVER_STOP " */
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <random>
using namespace std;
using namespace __gnu_pbds;
#define Code ios_base::sync_with_stdio(false);
#define By cin.tie(NULL);
#define NeverSpot cout.tie(NULL);
#define int long long
#define double long double
#define f first
#define s second
#define ed <<endl;
#define co cout<<
#define ci cin>>
#define sped <<" ";
#define sp <<" "<<
#define love cout<<" Insha " ed
#define all(x) (x).begin(),(x).end()
#define fl(a,b) for (int i=a;i<(b);++i)
#define rfl(a,b) for (int i=a;i>=(b);--i)
#define sl(a,b) for (int j=a;j<(b);++j)
#define rsl(a,b) for (int j=a;j>=(b);--j)
#define tl(a,b) for (int k=a;k<(b);++k)
#define rtl(a,b) for (int k=a;k>=(b);--k)
#define test(t) int t;cin>>t;for(int O=1;O<=t;O++)
#define sortv(v) sort(all(v));
#define sumv(arr) accumulate(all(arr),0LL)
#define rev(v) reverse(all(v));
#define ai(o,size) vi o;fl(0,size){int p ; cin>>p ; (o).push_back(p);}
#define Mod 1000000007ll
#define Emod 998244353ll
#define inf 1000000000000000009ll
#define gcd __gcd
inline int Sqrt(int x){ int y=static_cast<long long>(sqrt(x))+5;while(y*y>x)y--;return y;}
#define log2(x) (64 - __builtin_clzll(x) - 1) // log2 in O(1) time
using mii = map<long long, long long>;
using vi = vector<long long>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vvc = vector<vector<char>>;
using vc = vector<char>;
using vs = vector<string>;
using vvi = vector<vector<long long>>;
using vvp = vector<vector<pair<long long, long long>>>;
using pii = pair<long long, long long>;
using vp = vector<pair<long long, long long>>;
typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> order_set; // find_by_order, order_of_key
typedef tree<pair<int,int>, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> order_multiset; // find_by_order, order_of_key
string al="abcdefghijklmnopqrstuvwxyz";
//.........For Taking Mod............//
inline int power(int a, int b, int mod=Mod) {int res = 1; while (b > 0) {if (b & 1)res = res * a % mod; a = a * a % mod; b = b >> 1;} return res;}
class mod
{
static int mminvprime(int a, int b) {return power(a, b - 2, b);}
public:
int m=Mod;
void set(int m) {this->m=m;}
int add(int a, int b) {a = a % m; b = b % m; return ((a + b) % m + m) % m;}
int mul(int a, int b) {a = a % m; b = b % m; return (a * b % m + m) % m;}
int sub(int a, int b) {a = a % m; b = b % m; return ((a - b) % m + m) % m;}
int div(int a, int b) {a = a % m; b = b % m; return (mul(a, mminvprime(b, m)) + m) % m;} //only for prime m
}mod;
//.........Bit_Manipulation...........//
#define msb(mask) (63-__builtin_clzll(mask)) /// 0 -> -1
#define lsb(mask) __builtin_ctzll(mask) /// 0 -> 64
#define cntsetbit(mask) __builtin_popcountll(mask)
#define checkbit(mask,bit) ((mask >> bit) & 1ll)
#define onbit(mask,bit) ((mask)|(1LL<<(bit)))
#define offbit(mask,bit) ((mask)&~(1LL<<(bit)))
#define changebit(mask,bit) ((mask)^(1LL<<bit))
// random number generator #BESTEST_QUAILTY :)
mt19937_64 gen(random_device{}());
long long rng(int l=0,int r=INT64_MAX){uniform_int_distribution dist(l, r);return dist(gen);}
// Custom hashing for unordered map or set
const int RANDOM = rng();
struct chash{int operator()(int x) const { return x ^ RANDOM; }};
// Function
#define Ceil(a,b) ((a+b-1)/b)
#define print(arr) for(auto &o:(arr)){co o sped;} cout ed
#define mxe(v) *max_element(v.begin(),v.end()) // find max element in vector
#define mne(v) *min_element(v.begin(),v.end()) // find min element in vector
inline bool isPrime(int v) {if(v==1) return false; if(v <= 3)return true;if ( v % 2 == 0 || v % 3 == 0)return false;int i = 5;while (i * i <= v) {if (v % i == 0 || v % (i + 2) == 0)return false;i += 6;}return true;}
inline void printbin(int v,int upto=10) {cout<<v<<"-> ";for (int i = upto; i >= 0; --i) {cout<<checkbit(v,i) sped}cout ed}
bool isEqual(double a, double b, double epsilon = 1e-9) {return abs(a - b) <= epsilon * (1ll + max(abs(a), abs(b)));}
inline bool limit_check(long long a, long long b, int max_bits = 59) {if (a == 0 || b == 0) return true;return msb(a) + msb(b) >= 128 - max_bits;}
namespace std {
// fast swap
void swap(order_set &a, order_set &b) { a.swap(b); }
void swap(order_multiset &a, order_multiset &b) { a.swap(b); }
}
// Free to use :}
int best_path(int n, int k, int edges[][2], int weights[]) {// Global Variables
vvp e(n+1);
fl(0,n-1) {
auto [x,y]=edges[i];
e[x].push_back({y,weights[i]});
e[y].push_back({x,weights[i]});
}
vi dept(n+1,0);
vi cnt(n+1,0);
function<void(int, int)> dfs = [&](int v, int p) {
for (auto [child,w] : e[v]) {
if (child == p)continue;
dept[child]=dept[v]+w;
cnt[child]=cnt[v]+1;
dfs(child, v);
}
};
dfs(1,1);
vector<mii> data(n+1);
int ans=inf;
function<void(int, int)> cal = [&](int v, int p) {
int dl=dept[v];
int best=v;
data[v][dl]=cnt[v];
for (auto [child,w] : e[v]) {
if (child == p)continue;
cal(child, v);
if (data[child].size()>data[best].size())swap(child,best);
for (auto &[dis,cn]:data[child]) {
int want=k-dis+(2*dl);
if (data[best].contains(want)) {
int lc=data[best][want];
int rc=cn;
int sex=lc+rc-2*cnt[v];
ans=min(ans,sex);
}
}
for (auto &p:data[child]) {
if (data[best].contains(p.f)) {
data[best][p.f]=min(data[best][p.f],p.s);
}else {
data[best][p.f]=p.s;
}
}
}
swap(data[best],data[v]);
for (auto &p:data[best]) {
if (data[v].contains(p.f)) {
data[v][p.f]=min(data[v][p.f],p.s);
}else {
data[v][p.f]=p.s;
}
}
};
cal(1,1);
if (ans==inf) {
return -1;
}else {
return ans;
}
}