Submission #1707532
Source Code Expand
# include <iostream> # include <algorithm> # include <vector> # include <string> # include <set> # include <map> # include <cmath> # include <iomanip> # include <functional> # include <utility> # include <stack> # include <queue> # include <list> # include <bitset> # include <complex> # include <numeric> using namespace std; using LL = long long; using ULL = unsigned long long; constexpr long long MOD = 10007; constexpr int INF = 2000000000; constexpr int HINF = INF / 2; constexpr double DINF = 100000000000000000.0; constexpr long long LINF = 9000000000000000000; constexpr long long HLINF = 4500000000000000000; const double PI = acos(-1); constexpr int MAX_V = 100001; int V, E; vector<int> G[MAX_V]; int start, goal; int dis[MAX_V]; int bfs() { queue<int>que; for (int i = 0; i < MAX_V; i++)dis[i] = INF; que.push(start); dis[start] = 0; while (que.size()) { int p = que.front(); que.pop(); for (int i = 0; i < G[p].size(); i++) { if (dis[G[p][i]] == INF) { que.push(G[p][i]); dis[G[p][i]] = dis[p] + 1; } } } return dis[goal]; } int main() { cin >> V; E = V - 1; int a, b; for (int i = 0; i < E; i++) { cin >> a >> b; a--, b--; G[a].emplace_back(b); G[b].emplace_back(a); } int q; cin >> q; for (int i = 0; i < q; i++) { cin >> start >> goal; start--, goal--; cout << bfs() + 1 << endl; } }
Submission Info
Submission Time | |
---|---|
Task | D - 閉路 |
User | M3_cp |
Language | C++14 (GCC 5.4.1) |
Score | 30 |
Code Size | 1437 Byte |
Status | TLE |
Exec Time | 2104 ms |
Memory | 6272 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 30 / 30 | 0 / 70 | ||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt |
Subtask1 | 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 | 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 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask0_sample01.txt | AC | 3 ms | 2944 KB |
subtask0_sample02.txt | AC | 2 ms | 2944 KB |
subtask0_sample03.txt | AC | 2 ms | 2944 KB |
subtask1_01.txt | AC | 68 ms | 6144 KB |
subtask1_02.txt | AC | 67 ms | 6144 KB |
subtask1_03.txt | AC | 2 ms | 2944 KB |
subtask1_04.txt | AC | 2 ms | 2944 KB |
subtask1_05.txt | AC | 3 ms | 3072 KB |
subtask1_06.txt | AC | 3 ms | 3072 KB |
subtask1_07.txt | AC | 77 ms | 6272 KB |
subtask1_08.txt | AC | 78 ms | 6144 KB |
subtask1_09.txt | AC | 78 ms | 6144 KB |
subtask1_10.txt | AC | 78 ms | 6144 KB |
subtask1_11.txt | AC | 79 ms | 6144 KB |
subtask1_12.txt | AC | 79 ms | 6144 KB |
subtask2_01.txt | TLE | 2104 ms | 6144 KB |
subtask2_02.txt | TLE | 2104 ms | 6144 KB |
subtask2_03.txt | TLE | 2103 ms | 3072 KB |
subtask2_04.txt | TLE | 2104 ms | 3072 KB |
subtask2_05.txt | TLE | 2103 ms | 3072 KB |
subtask2_06.txt | TLE | 2103 ms | 3072 KB |
subtask2_07.txt | TLE | 2104 ms | 6272 KB |
subtask2_08.txt | TLE | 2104 ms | 6144 KB |
subtask2_09.txt | TLE | 2104 ms | 6144 KB |
subtask2_10.txt | TLE | 2104 ms | 6144 KB |
subtask2_11.txt | TLE | 2104 ms | 6144 KB |
subtask2_12.txt | TLE | 2104 ms | 6144 KB |