AtCoder Beginner Contest 014

Submission #1678451

Source codeソースコード

#include <bits/stdc++.h>

#define REP(i,n) for(int i=0;i<(n);++i)
#define FORR(it,cont) for(auto it=rbegin(cont);it!=rend(cont);++it)
#define FOR(it,cont) for(auto it=begin(cont);it!=end(cont);++it)
#define ALL(cont) begin(cont), end(cont)
#define LB(b,e,v) lower_bound(b,e,v)
#define UB(b,e,v) upper_bound(b,e,v)
#define AS_MOD(a,b) ((((a) % (b) ) + (b)) % (b))
#define MODDING(a,b) (a) = AS_MOD(a,b)
#define MAXIMIZE(a, b) (a) = max((a),(b))
#define MINIMIZE(a, b) (a) = min((a),(b))

using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<int, Pii> iPii;
struct SegmentTree {
  vector<int> Storage;
  int N;

  void init(int n) {
    N = 1;
    while (N < n) N *= 2;
    Storage.resize(N * 2);
    for (int i = 0; i < N * 2; ++i) {
      Storage[i] = 0;
    }
  }

  void updateLeaf(int i, int value) {
    i += N - 1;
    Storage[i] = value;
    while (i > 0) {
      i = (i - 1) / 2;
      Storage[i] = min(Storage[i * 2 + 1], Storage[i * 2 + 2]);
    }
  }

  int calcRangeGCD(int a, int b, int k, int l, int r) {
    if (b <= l || a >= r) return 0;
    if (a <= l && b >= r) {
      return Storage[k];
    } else {
      int tl = calcRangeGCD(a, b, k * 2 + 1, l, (l + r) / 2);
      int tr = calcRangeGCD(a, b, k * 2 + 2, (l + r) / 2, r);
      return min(tl, tr);
    }
  }
};
SegmentTree segTree;
int N;
vector<vector<int>> Graph;
vector<int> vindex;
vector<int> depthTable;
vector<bool> visited;
vector<int> vs;
void dfs(int cur, int depth) {
  visited[cur]=true;
  if (vindex[cur]==-1) {
    vindex[cur]=vs.size();
  }
  vs.push_back(cur);
  depthTable.push_back(depth);
  for(int e:Graph[cur]) {
    if (!visited[e]) {
      dfs(e, depth+1);
      vs.push_back(cur);
      depthTable.push_back(depth);
    }
  }
}
int main(int argc, char **argv, char **envp) {
  cin >> N;
  Graph.resize(N);
  vindex.resize(N, -1);
  visited.resize(N, false);
  segTree.init(N*2);
  REP(i, N-1) {
    int x,y;
    scanf("%d%d", &x, &y);--x;--y;
    Graph[x].push_back(y);
    Graph[y].push_back(x);
  }
  dfs(0,0);
  for(int i=0;i<2*N;++i) {
    segTree.updateLeaf(i, depthTable[i]);
  }
  int Q;
  cin >> Q;
  REP(i, Q) {
    int a,b;
    scanf("%d%d", &a, &b);--a;--b;
    a=vindex[a];b=vindex[b];
    if (b<a) {
      swap(a,b);
    }
    int val=segTree.calcRangeGCD(a,b+1,0,0,segTree.N);
    printf("%d\n",depthTable[a]+depthTable[b]-val-val+1);
  }


  return 0;
}

Submission

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

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main(int, char**, char**)’:
./Main.cpp:81:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);--x;--y;
^
./Main.cpp:93:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);--a;--b;
^

Test case

Set

Set name Score得点 / Max score Cases
Sample - subtask0_sample01.txt,subtask0_sample02.txt,subtask0_sample03.txt
Subtask1 0 / 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 0 / 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 WA
subtask1_01.txt AC 47 ms 14500 KB
subtask1_02.txt WA
subtask1_03.txt WA
subtask1_04.txt WA
subtask1_05.txt WA
subtask1_06.txt WA
subtask1_07.txt WA
subtask1_08.txt WA
subtask1_09.txt WA
subtask1_10.txt WA
subtask1_11.txt WA
subtask1_12.txt WA
subtask2_01.txt AC 81 ms 15260 KB
subtask2_02.txt WA
subtask2_03.txt WA
subtask2_04.txt WA
subtask2_05.txt WA
subtask2_06.txt WA
subtask2_07.txt WA
subtask2_08.txt WA
subtask2_09.txt WA
subtask2_10.txt WA
subtask2_11.txt WA
subtask2_12.txt WA