oj.uz

Submission #672203

# Submission time Handle Problem Language Result Execution time Memory
672203 2022-12-15T04:08:35 Z Ai7081 Miners (IOI07_miners) C++17
0 / 100
 15 ms 2516 KB 
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAXN = 5e5 + 10;
const int INF = 0x3f3f3f3f;

int N, M, S;
int h[MAXN], e[MAXN], ne[MAXN], idx;
int depth[MAXN], fa[MAXN][21];
int ans[MAXN];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u, int father)
{
    depth[u] = depth[father] + 1;
    fa[u][0] = father;
    for (int i = 1; i <= 20; i ++ )
        fa[u][i] = fa[fa[u][i - 1]][i - 1];

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;
        dfs(j, u);
    }
}

int lca(int a, int b)
{
    if (depth[a] < depth[b]) swap(a, b);
    for (int k = 20; ~k; k -- )
        if (depth[fa[a][k]] >= depth[b])
            a = fa[a][k];

    if (a == b) return a;
    for (int k = 20; ~k; k -- )
        if (fa[a][k] != fa[b][k])
            a = fa[a][k], b = fa[b][k];
    return fa[a][0];
}

int main()
{
    scanf("%d%d%d", &N, &M, &S);
    memset(h, -1, sizeof h);
    while (M -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }

    dfs(1, 0);

    while (S -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        int lca1 = lca(a, b), lca2 = lca(b, c), lca3 = lca(c, a);
        int LCA = lca(lca1, lca2);
        LCA = lca(lca3, LCA);

        if (LCA == lca1 || LCA == lca2 || LCA == lca3) ans[LCA] ++ ;
    }

    for (int i = 1; i <= N; i ++ )
        printf("%d\n", ans[i]);

    return 0;
}

Compilation message

miners.cpp: In function 'int main()':
miners.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     scanf("%d%d%d", &N, &M, &S);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
miners.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         scanf("%d%d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~
miners.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         scanf("%d%d%d", &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2224 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2232 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 2448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 2516 KB Output isn't correct
2 Halted 0 ms 0 KB -