Submission #1478641


Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

const int MaxN = 2e5 + 5;

vector<int> gb[MaxN], gr[MaxN];

int dep[MaxN], fa[MaxN], d[MaxN];
bool safe[MaxN], vis[MaxN];

void Dfs(int x, int f) {
  ::fa[x] = f;
  for (int k : gb[x]) {
    if (k != f) {
      dep[k] = dep[x] + 1;
      Dfs(k, x);
    }
  }
}

#define fin cin
#define fout cout

int main() {
  ios_base::sync_with_stdio(false);
  int n, sx, sy;
  fin >> n >> sx >> sy;
  for (int i = 1; i < n; ++i) {
    int x, y;
    fin >> x >> y;
    gr[x].emplace_back(y);
    gr[y].emplace_back(x);
  }
  for (int i = 1; i < n; ++i) {
    int x, y;
    fin >> x >> y;
    gb[x].emplace_back(y);
    gb[y].emplace_back(x);
  }
  Dfs(sy, -1);
  for (int i = 1; i <= n; ++i) {
    for (int k : gr[i]) {
      if (![](int x, int y) -> bool {
        return fa[x] == fa[y] || fa[x] == y || x == fa[y] || fa[fa[x]] == y || x == fa[fa[y]];
      } (i, k)) {
        safe[i] = safe[k] = true;
      }
    }
  }
  if (safe[sx]) {
    fout << -1 << endl;
    return 0;
  }
  int ans = 0;
  memset(d, 0xff, sizeof d);
  d[sx] = 0;
  queue<int> Q;
  Q.push(sx);
  while (!Q.empty()) {
    int k = Q.front();
    Q.pop();
    if (d[k] >= dep[k]) {
      continue;
    }
    if (safe[k]) {
      fout << -1 << endl;
      return 0;
    }
    ans = max(ans, dep[k] * 2);
    for (int x : gr[k]) {
      if (!vis[x] && d[k] + 1 < dep[x] && [](int x, int y) -> bool {
        return fa[x] == fa[y] || fa[x] == y || x == fa[y] || fa[fa[x]] == y || x == fa[fa[y]];
        } (k, x)) {
        d[x] = d[k] + 1;
        vis[x] = true;
        Q.push(x);
      }
    }
  }
  fout << ans << endl;
  return 0;
}

Submission Info

Submission Time
Task E - Sugigma: The Showdown
User Forest_Timber
Language C++14 (GCC 5.4.1)
Score 1400
Code Size 1861 Byte
Status AC
Exec Time 154 ms
Memory 33532 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1400 / 1400
Status
AC × 5
AC × 103
Set Name Test Cases
Sample example0, example1, example2, example3, example4
All doublestar0, doublestar1, doublestar2, doublestar3, doublestar4, doublestar5, doublestar6, doublestar7, example0, example1, example2, example3, example4, giri0, giri1, giri2, giri3, giri4, giri5, giri6, giri7, giri8, giri9, maxrand0, maxrand1, maxrand2, maxrand3, maxrand4, maxrand5, maxrand6, maxrand7, maxrand8, maxrand9, narashi0, narashi1, narashi2, narashi3, narashi4, narashi5, narashi6, narashi7, narashi8, narashi9, ok0, ok1, ok2, ok3, ok4, ok5, ok6, ok7, ok8, ok9, ouh0, ouh1, ouh2, ouh3, ouh4, ouh5, ouh6, ouh7, ouh8, ouh9, same0, same1, same2, same3, same4, same5, same6, same7, same8, same9, sameline0, sameline1, sameline2, sameline3, sameline4, sameline5, sameline6, sameline7, sameline8, sameline9, star0, star1, star2, star3, star4, star5, star6, star7, star8, star9, supersmall0, supersmall1, supersmall2, supersmall3, supersmall4, supersmall5, supersmall6, supersmall7, supersmall8, supersmall9
Case Name Status Exec Time Memory
doublestar0 AC 128 ms 24312 KB
doublestar1 AC 118 ms 23672 KB
doublestar2 AC 126 ms 24056 KB
doublestar3 AC 114 ms 23416 KB
doublestar4 AC 139 ms 24568 KB
doublestar5 AC 140 ms 24568 KB
doublestar6 AC 131 ms 23544 KB
doublestar7 AC 127 ms 23544 KB
example0 AC 5 ms 11136 KB
example1 AC 5 ms 11136 KB
example2 AC 5 ms 11136 KB
example3 AC 4 ms 10368 KB
example4 AC 5 ms 11136 KB
giri0 AC 136 ms 25728 KB
giri1 AC 143 ms 24704 KB
giri2 AC 138 ms 24832 KB
giri3 AC 142 ms 24832 KB
giri4 AC 143 ms 24704 KB
giri5 AC 147 ms 25216 KB
giri6 AC 150 ms 25088 KB
giri7 AC 142 ms 24960 KB
giri8 AC 149 ms 24832 KB
giri9 AC 137 ms 25088 KB
maxrand0 AC 143 ms 24320 KB
maxrand1 AC 139 ms 24064 KB
maxrand2 AC 148 ms 24320 KB
maxrand3 AC 144 ms 23936 KB
maxrand4 AC 139 ms 23680 KB
maxrand5 AC 137 ms 23808 KB
maxrand6 AC 138 ms 23808 KB
maxrand7 AC 143 ms 24064 KB
maxrand8 AC 139 ms 23680 KB
maxrand9 AC 140 ms 24064 KB
narashi0 AC 139 ms 24320 KB
narashi1 AC 140 ms 24448 KB
narashi2 AC 136 ms 24704 KB
narashi3 AC 140 ms 24960 KB
narashi4 AC 146 ms 24832 KB
narashi5 AC 147 ms 24960 KB
narashi6 AC 144 ms 24704 KB
narashi7 AC 145 ms 25216 KB
narashi8 AC 146 ms 24960 KB
narashi9 AC 137 ms 24576 KB
ok0 AC 146 ms 32124 KB
ok1 AC 149 ms 33148 KB
ok2 AC 147 ms 30076 KB
ok3 AC 153 ms 33532 KB
ok4 AC 146 ms 28160 KB
ok5 AC 150 ms 30076 KB
ok6 AC 151 ms 30588 KB
ok7 AC 142 ms 28032 KB
ok8 AC 153 ms 31740 KB
ok9 AC 143 ms 30716 KB
ouh0 AC 122 ms 26496 KB
ouh1 AC 138 ms 27264 KB
ouh2 AC 128 ms 27136 KB
ouh3 AC 139 ms 28032 KB
ouh4 AC 143 ms 27648 KB
ouh5 AC 138 ms 30844 KB
ouh6 AC 143 ms 31996 KB
ouh7 AC 132 ms 27136 KB
ouh8 AC 146 ms 30588 KB
ouh9 AC 146 ms 31996 KB
same0 AC 146 ms 24960 KB
same1 AC 146 ms 24832 KB
same2 AC 141 ms 25088 KB
same3 AC 141 ms 25088 KB
same4 AC 138 ms 24576 KB
same5 AC 145 ms 24576 KB
same6 AC 139 ms 24832 KB
same7 AC 145 ms 24704 KB
same8 AC 134 ms 24448 KB
same9 AC 149 ms 25088 KB
sameline0 AC 147 ms 32128 KB
sameline1 AC 154 ms 32768 KB
sameline2 AC 145 ms 30336 KB
sameline3 AC 148 ms 31232 KB
sameline4 AC 147 ms 32256 KB
sameline5 AC 151 ms 32000 KB
sameline6 AC 146 ms 29312 KB
sameline7 AC 152 ms 31872 KB
sameline8 AC 149 ms 30720 KB
sameline9 AC 153 ms 29568 KB
star0 AC 106 ms 25588 KB
star1 AC 98 ms 26484 KB
star2 AC 95 ms 25588 KB
star3 AC 102 ms 25460 KB
star4 AC 104 ms 25588 KB
star5 AC 106 ms 26740 KB
star6 AC 97 ms 25716 KB
star7 AC 101 ms 25588 KB
star8 AC 100 ms 25460 KB
star9 AC 111 ms 26996 KB
supersmall0 AC 4 ms 10368 KB
supersmall1 AC 4 ms 10368 KB
supersmall2 AC 5 ms 11136 KB
supersmall3 AC 5 ms 11136 KB
supersmall4 AC 4 ms 10368 KB
supersmall5 AC 5 ms 11136 KB
supersmall6 AC 4 ms 10368 KB
supersmall7 AC 5 ms 11136 KB
supersmall8 AC 5 ms 11136 KB
supersmall9 AC 5 ms 11136 KB