AtCoder Beginner Contest 014

Submission #7466359

Source codeソースコード

#include<bits/stdc++.h>
using namespace std;

#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define spa << " " <<
#define lfs <<fixed<<setprecision(10)<<
#define test cout<<"test"<<endl;
#define fi first
#define se second
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define rep(i,n,m) for(ll i = n; i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = n - 1; i >= (ll)(m); i--)
typedef long long ll;
typedef long double ld;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const ll INF = 1e18;
using P = pair<ll, ll>;
template<typename T>
void chmin(T &a,T b){if(a>b)a=b;}
template<typename T>
void chmax(T &a,T b){if(a<b)a=b;}
void pmod(ll &a,ll b){a=(a+b)%MOD;}
void pmod(ll &a,ll b,ll c){a=(b+c)%MOD;}
void qmod(ll &a,ll b){a=(a*b)%MOD;}
void qmod(ll &a,ll b,ll c){a=(b*c)%MOD;}
ll median(ll a,ll b, ll c){return a+b+c-max({a,b,c})-min({a,b,c});}
void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
template<typename T1,typename T2>
void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}  
template<typename T>
void debug(vector<vector<T>>v,ll h,ll w){for(ll i=0;i<h;i++)
{cout<<v[i][0];for(ll j=1;j<w;j++)cout spa v[i][j];cout<<endl;}};
void debug(vector<string>v,ll h,ll w){for(ll i=0;i<h;i++)
{for(ll j=0;j<w;j++)cout<<v[i][j];cout<<endl;}};
template<typename T>
void debug(vector<T>v,ll n){cout<<v[0];
for(ll i=1;i<n;i++)cout spa v[i];cout<<endl;};
template<typename T>
vector<vector<T>>vec(ll x, ll y, T w){
  vector<vector<T>>v(x,vector<T>(y,w));return v;}
ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;}
template<typename T>
void emp(map<T,ll>&m, T x){m.emplace(x,0).first->second++;}
vector<ll>dx={1,0,-1,0,1,1,-1,-1};
vector<ll>dy={0,1,0,-1,1,-1,1,-1};

struct LCA{
  ll datasize = 21;
  ll n,root;//rootを根とする頂点数nの根付き木
  vector<ll>depth;//0から
  vector<vector<ll>>G,data;
  LCA(vector<vector<ll>>g,ll r):G(g),n(g.size()),root(r){
    data.assign(n,vector<ll>(datasize,-1));
    depth.assign(n,-1LL);
    build();
  }
  void build(){
    dfs(root,0);
    for(ll i=1;i<datasize;i++){
      for(ll j=0;j<n;j++){
        if(data[j][i-1]==-1)data[j][i]=-1;
        else data[j][i]=data[data[j][i-1]][i-1];
      }
    }
  }
  void dfs(ll k,ll d){
    depth[k]=d;
    for(ll i=0;i<G[k].size();i++){
      if(depth[G[k][i]]==-1){
        data[G[k][i]][0]=k;
        dfs(G[k][i],d+1);
      }
    }
  }
  ll deep(ll x){
    return x>=0?depth[x]:-1;
  }
  ll query(ll x,ll y){
    if(depth[x]<depth[y])swap(x,y);
    ll tmp = datasize - 1;
    while(depth[x]!=depth[y]){
      while(tmp>=1&&depth[y]>=deep(data[x][tmp]))tmp--;
      x = data[x][tmp];
    }
    tmp = datasize - 1;
    while(x!=y){
      while(tmp>=1&&data[x][tmp]==data[y][tmp])tmp--;
      x = data[x][tmp];
      y = data[y][tmp];
    }
    return x;
  }
};

int main(){
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);
  ll res=0,res1=INF,res2=-INF,buf=0;
  bool judge = true;
  ll n;cin>>n;
  vector<vector<ll>>g(n);
  for(ll i=0;i<n-1;i++){
    ll p,q;
    cin>>p>>q;
    g[p-1].push_back(q-1);
    g[q-1].push_back(p-1);
  }
  struct LCA lca(g,0);
  ll q;cin>>q;
  rep(i,0,q){
    ll a,b;cin>>a>>b;
    a--;b--;
    ll x=lca.query(a,b);
    cout<<lca.deep(a)+lca.deep(b)-2*lca.deep(x)+1<<endl;
  }
  return 0;
}

Submission

Task問題 D - 閉路
User nameユーザ名 tute7627
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 3579 Byte
File nameファイル名
Exec time実行時間 343 ms
Memory usageメモリ使用量 40448 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 1 ms 256 KB
subtask0_sample02.txt AC 1 ms 256 KB
subtask0_sample03.txt AC 1 ms 256 KB
subtask1_01.txt AC 72 ms 40448 KB
subtask1_02.txt AC 72 ms 40448 KB
subtask1_03.txt AC 1 ms 256 KB
subtask1_04.txt AC 1 ms 256 KB
subtask1_05.txt AC 2 ms 640 KB
subtask1_06.txt AC 2 ms 640 KB
subtask1_07.txt AC 94 ms 38144 KB
subtask1_08.txt AC 97 ms 37888 KB
subtask1_09.txt AC 95 ms 37760 KB
subtask1_10.txt AC 105 ms 37760 KB
subtask1_11.txt AC 107 ms 37760 KB
subtask1_12.txt AC 98 ms 37760 KB
subtask2_01.txt AC 248 ms 40448 KB
subtask2_02.txt AC 252 ms 40448 KB
subtask2_03.txt AC 171 ms 512 KB
subtask2_04.txt AC 175 ms 512 KB
subtask2_05.txt AC 184 ms 896 KB
subtask2_06.txt AC 187 ms 1024 KB
subtask2_07.txt AC 290 ms 38144 KB
subtask2_08.txt AC 301 ms 37888 KB
subtask2_09.txt AC 312 ms 37760 KB
subtask2_10.txt AC 322 ms 37760 KB
subtask2_11.txt AC 343 ms 37760 KB
subtask2_12.txt AC 342 ms 37760 KB