Submission #848407

#	Time	Username	Problem	Language	Result	Execution time	Memory
848407		Essa2006	Treasure Hunt (CEOI11_tre)	C++14	50 / 100	1847 ms	262144 KiB

Main

#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
 
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
 
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
using namespace std;
#define ll long long
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
const int lg=20;
int cur=2;
vector<ll>Dep, Upd(lg+1), Lvl;
vector<vector<ll> >Lca, Dis;

int find_lca(int u, int v){
    // u
    
    // v
    if(Lvl[v]<Lvl[u])
        swap(u, v);
    for(int i=lg;i>=0;i--){
        if(Lvl[Lca[v][i]]>Lvl[u])
            v=Lca[v][i];
    }
    if(Lvl[u]!=Lvl[v])
        v=Lca[v][0];
    if(u==v)
        return u;
    for(int i=lg;i>=0;i--){
        if(Lca[u][i]!=Lca[v][i])
            u=Lca[u][i], v=Lca[v][i];
    }
    u=Lca[u][0], v=Lca[v][0];
    return u;
}
void init(){
    Dep.push_back(0);
    Dep.push_back(0);
    Lvl.push_back(0);
    Lvl.push_back(0);
    Lca.push_back(Upd);
    Lca.push_back(Upd);
    Dis.push_back(Upd);
    Dis.push_back(Upd);
}


void path(int a, int s){
    for(int i=0;i<s;i++){
        int u=cur++;
        Dep.push_back(Dep[a]+1);
        Lvl.push_back(Lvl[a]+1);
        Lca.push_back(Upd);
        Dis.push_back(Upd);
        Lca[u][0]=a, Dis[u][0]=1;
        for(int j=1;j<=lg;j++){
            Lca[u][j]=Lca[Lca[u][j-1]][j-1];
            Dis[u][j]=Dis[u][j-1]+Dis[Lca[u][j-1]][j-1];
            
        }
        a=u;
    }
}

int dig(int u, int v){
    int lca=find_lca(u, v);
    ll dis=Dep[u]+Dep[v]-2*Dep[lca];
    ll travel=(dis)/2;
    ll u_to_lca=0;
    int real_u=u;
    for(int j=lg;j>=0;j--){
        if(Lvl[Lca[u][j]]>Lvl[lca] && Lca[u][j]>=1)
            u_to_lca+=Dis[u][j], u=Lca[u][j];
    }
    if(u!=lca)
        u_to_lca+=Dis[u][0], u=Lca[u][0];
    u=real_u;
    ll real_dis=0;
    if(u_to_lca>=dis-u_to_lca){
        for(int j=lg;j>=0;j--){
            if(real_dis+Dis[u][j]<=travel && Lca[u][j]>=1)
                real_dis+=Dis[u][j], u=Lca[u][j];
        }
    }
    else{
        swap(u, v);
        for(int j=lg;j>=0;j--){
            if(real_dis+Dis[u][j]<=travel && Lca[u][j]>=1)
                real_dis+=Dis[u][j], u=Lca[u][j];
        }
        if(dis&1)
            u=Lca[u][0];
    }
    
    return u;
}

//int main()
//{
//  int num_calls;
//  scanf("%d", &num_calls);
//  for (int i = 1; i <= num_calls; i++)
//  {
//    char call[2];
//    int a, b;
//    scanf("%s%d%d", call, &a, &b);
//    if (call[0] == 'i')
//      init();
//    else if (call[0] == 'p')
//      path(a, b);
//    else
//      printf("%d\n", dig(a, b));
//  }
//  return 0;
//}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10