AtCoder Beginner Contest 014

Submission #6900818

Source codeソースコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}
const int V_MAX = 1e5+10;
int V;
vector<vector<int> > G(V_MAX);

template< typename G >
struct DoublingLowestCommonAncestor{
  const int LOG;
  vector<int> dep;
  const G &g;
  vector<vector<int> > table;

  DoublingLowestCommonAncestor(const G &g) : g(g), dep(g.size()), LOG(32 - __builtin_clz(g.size())) {
    table.assign(LOG, vector<int>(g.size(),-1));
  }

  void dfs(int idx, int par, int d){
    table[0][idx] = par;
    dep[idx] = d;
    for(auto & to : g[idx]){
      if(to != par) dfs(to, idx, d+1);
    }
  }

  void build(){
    dfs(0,-1,0);
    rep(k,LOG-1){
      rep(i,table[k].size()){
        if(table[k][i] == -1) table[k+1][i] = -1;
        else table[k+1][i] = table[k][table[k][i]];
      }
    }
  }

  int query(int u, int v){
    if(dep[u] > dep[v])swap(u,v);
    per(i,LOG) if(((dep[v] - dep[u]) >> i) & 1) v = table[i][v];
    if(u==v) return u;
    per(i,LOG){
      if(table[i][u] != table[i][v]){
        u = table[i][u];
        v = table[i][v];
      }
    }
    return table[0][u];
  }
};


vector<vector<int> > makeTree(const vector<vector<int> > &G){
 vector<vector<int> > Tree(V);
 set<int> st;
 queue<int> que;
 que.push(0);
 st.insert(0);
 while(!que.empty()){
   int cur = que.front();que.pop();
   for(const int & v : G[cur]){
     if(st.count(v))continue;
     st.insert(v);
     que.push(v);
     Tree[cur].push_back(v);
   }
 }
 return Tree;
}

void outTree(const vector<vector<int> > &Tree){
  queue<int> que;
  que.push(0);
  while(!que.empty()){
    int cur = que.front();que.pop();
    for(const int &v : Tree[cur]){
      cout << cur SP v << endl;
      que.push(v);
    }
  }
}

int main(void){
  SPEEDUP
  cout << setprecision(15);
  cin >> V;
  rep(i,V-1){
    int v,u;cin >> v >> u;
    --v,--u;
    G[v].push_back(u);
    G[u].push_back(v);
  }
  vector<vector<int> > Tree = makeTree(G);
  DoublingLowestCommonAncestor< vector<vector<int> > > lca(Tree);
  lca.build();
  int Q;cin >> Q;
  while(Q--){
    int u,v;cin >> u >> v;
    --u;--v;
    cout << lca.dep[u] + lca.dep[v] - 2*lca.dep[lca.query(u,v)] + 1 << endl;
  }
  //outTree(Tree);
  //rep(v,V)cout << lca.dep[v] SPF;
  //cout << endl;
  return 0;
}

Submission

Task問題 D - 閉路
User nameユーザ名 issei
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 3360 Byte
File nameファイル名
Exec time実行時間 371 ms
Memory usageメモリ使用量 26616 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - subtask0_sample01.txt,subtask0_sample02.txt,subtask0_sample03.txt
Subtask1 30 / 30 subtask1_01.txt,subtask1_02.txt,subtask1_03.txt,subtask1_04.txt,subtask1_05.txt,subtask1_06.txt,subtask1_07.txt,subtask1_08.txt,subtask1_09.txt,subtask1_10.txt,subtask1_11.txt,subtask1_12.txt
Subtask2 70 / 70 subtask0_sample01.txt,subtask0_sample02.txt,subtask0_sample03.txt,subtask1_01.txt,subtask1_02.txt,subtask1_03.txt,subtask1_04.txt,subtask1_05.txt,subtask1_06.txt,subtask1_07.txt,subtask1_08.txt,subtask1_09.txt,subtask1_10.txt,subtask1_11.txt,subtask1_12.txt,subtask2_01.txt,subtask2_02.txt,subtask2_03.txt,subtask2_04.txt,subtask2_05.txt,subtask2_06.txt,subtask2_07.txt,subtask2_08.txt,subtask2_09.txt,subtask2_10.txt,subtask2_11.txt,subtask2_12.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask0_sample01.txt AC 3 ms 2816 KB
subtask0_sample02.txt AC 2 ms 2560 KB
subtask0_sample03.txt AC 2 ms 2560 KB
subtask1_01.txt AC 84 ms 25848 KB
subtask1_02.txt AC 83 ms 25848 KB
subtask1_03.txt AC 2 ms 2560 KB
subtask1_04.txt AC 3 ms 2560 KB
subtask1_05.txt AC 3 ms 2816 KB
subtask1_06.txt AC 3 ms 2816 KB
subtask1_07.txt AC 127 ms 21888 KB
subtask1_08.txt AC 129 ms 22144 KB
subtask1_09.txt AC 144 ms 22272 KB
subtask1_10.txt AC 141 ms 22272 KB
subtask1_11.txt AC 141 ms 22272 KB
subtask1_12.txt AC 137 ms 22272 KB
subtask2_01.txt AC 262 ms 26616 KB
subtask2_02.txt AC 256 ms 26488 KB
subtask2_03.txt AC 169 ms 2816 KB
subtask2_04.txt AC 168 ms 2816 KB
subtask2_05.txt AC 179 ms 3072 KB
subtask2_06.txt AC 182 ms 3200 KB
subtask2_07.txt AC 350 ms 21888 KB
subtask2_08.txt AC 356 ms 22144 KB
subtask2_09.txt AC 365 ms 22272 KB
subtask2_10.txt AC 363 ms 22272 KB
subtask2_11.txt AC 371 ms 22272 KB
subtask2_12.txt AC 369 ms 22272 KB