Submission #34397172
Source Code Expand
Copy
#include <bits/stdc++.h>#define P pair<int, int>#define fi first#define se second#define pb push_back#define all(v) v.begin(), v.end()using namespace std;template <typename T> void rd(T &x) {x = 0; T f = 1; char ch = getchar();while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}x *= f;}template <typename T> void write(T x) {if (x < 0) {putchar('-'); x = -x;}if (x >= 10) write(x / 10);putchar(x % 10 + 48);}typedef long long ll;const int N = 2e5 + 10;
#include <bits/stdc++.h> #define P pair<int, int> #define fi first #define se second #define pb push_back #define all(v) v.begin(), v.end() using namespace std; template <typename T> void rd(T &x) { x = 0; T f = 1; char ch = getchar(); while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();} while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();} x *= f; } template <typename T> void write(T x) { if (x < 0) {putchar('-'); x = -x;} if (x >= 10) write(x / 10); putchar(x % 10 + 48); } typedef long long ll; const int N = 2e5 + 10; const int INF = 0x3f3f3f3f; const int Mod = 1e9 + 7; int n; vector<int> G[N]; int f[N], deg[N]; bool vis[N]; void dfs(int u, int fa, int col) { f[u] = col; for (auto v : G[u]) { if (v == fa || !vis[v]) continue; dfs(v, u, col); } } int main() { rd(n); for (int i = 1; i <= n; i++) { int u, v; rd(u); rd(v); G[u].pb(v); G[v].pb(u); deg[v]++; deg[u]++; f[i] = i; } queue<int> q; for (int i = 1; i <= n; i++) if (deg[i] == 1) q.push(i); while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = 1; for (auto v : G[u]) { deg[v]--; if (deg[v] == 1) q.push(v); } } for (int i = 1; i <= n; i++) { if (!vis[i]) { dfs(i, 0, i); } } int Q; rd(Q); while (Q--) { int x, y; rd(x); rd(y); if (f[x] == f[y]) puts("Yes"); else puts("No"); } return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Well-defined Path Queries on a Namori |
User | LYR_ |
Language | C++ (GCC 9.2.1) |
Score | 500 |
Code Size | 1661 Byte |
Status | AC |
Exec Time | 98 ms |
Memory | 28612 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 500 / 500 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 00_sample_01.txt, 00_sample_02.txt |
All | 00_sample_01.txt, 00_sample_02.txt, 01_test_01.txt, 01_test_02.txt, 01_test_03.txt, 01_test_04.txt, 01_test_05.txt, 01_test_06.txt, 01_test_07.txt, 01_test_08.txt, 01_test_09.txt, 01_test_10.txt, 01_test_11.txt, 01_test_12.txt, 01_test_13.txt, 01_test_14.txt, 01_test_15.txt, 01_test_16.txt, 01_test_17.txt, 01_test_18.txt, 01_test_19.txt, 01_test_20.txt, 01_test_21.txt, 01_test_22.txt, 01_test_23.txt, 01_test_24.txt, 01_test_25.txt, 01_test_26.txt, 01_test_27.txt, 01_test_28.txt, 01_test_29.txt, 01_test_30.txt, 02_handmade_01.txt, 02_handmade_02.txt, 02_handmade_03.txt, 02_handmade_04.txt, 02_handmade_05.txt, 02_handmade_06.txt, 02_handmade_07.txt, 02_handmade_08.txt, 02_handmade_09.txt, 02_handmade_10.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_01.txt | AC | 19 ms | 8088 KB |
00_sample_02.txt | AC | 7 ms | 8236 KB |
01_test_01.txt | AC | 9 ms | 8060 KB |
01_test_02.txt | AC | 8 ms | 8080 KB |
01_test_03.txt | AC | 7 ms | 8084 KB |
01_test_04.txt | AC | 10 ms | 8048 KB |
01_test_05.txt | AC | 7 ms | 8228 KB |
01_test_06.txt | AC | 7 ms | 8072 KB |
01_test_07.txt | AC | 9 ms | 8040 KB |
01_test_08.txt | AC | 7 ms | 8076 KB |
01_test_09.txt | AC | 8 ms | 8176 KB |
01_test_10.txt | AC | 6 ms | 8292 KB |
01_test_11.txt | AC | 47 ms | 12540 KB |
01_test_12.txt | AC | 46 ms | 11864 KB |
01_test_13.txt | AC | 25 ms | 8380 KB |
01_test_14.txt | AC | 80 ms | 16380 KB |
01_test_15.txt | AC | 46 ms | 11944 KB |
01_test_16.txt | AC | 39 ms | 10216 KB |
01_test_17.txt | AC | 61 ms | 13784 KB |
01_test_18.txt | AC | 74 ms | 15312 KB |
01_test_19.txt | AC | 65 ms | 13772 KB |
01_test_20.txt | AC | 82 ms | 16164 KB |
01_test_21.txt | AC | 95 ms | 16596 KB |
01_test_22.txt | AC | 96 ms | 16424 KB |
01_test_23.txt | AC | 89 ms | 16724 KB |
01_test_24.txt | AC | 98 ms | 16700 KB |
01_test_25.txt | AC | 91 ms | 16840 KB |
01_test_26.txt | AC | 84 ms | 16820 KB |
01_test_27.txt | AC | 89 ms | 16892 KB |
01_test_28.txt | AC | 91 ms | 16892 KB |
01_test_29.txt | AC | 88 ms | 16704 KB |
01_test_30.txt | AC | 91 ms | 16848 KB |
02_handmade_01.txt | AC | 71 ms | 16868 KB |
02_handmade_02.txt | AC | 70 ms | 16684 KB |
02_handmade_03.txt | AC | 62 ms | 16324 KB |
02_handmade_04.txt | AC | 64 ms | 16516 KB |
02_handmade_05.txt | AC | 51 ms | 16060 KB |
02_handmade_06.txt | AC | 61 ms | 28512 KB |
02_handmade_07.txt | AC | 62 ms | 28612 KB |
02_handmade_08.txt | AC | 61 ms | 28604 KB |
02_handmade_09.txt | AC | 59 ms | 28568 KB |
02_handmade_10.txt | AC | 60 ms | 28612 KB |