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;
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#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
AC × 2
AC × 42
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


2025-02-28 (Fri)
05:16:16 +00:00