Submission #672203

#	Time	Username	Problem	Language	Result	Execution time	Memory
672203		Ai7081	Miners (IOI07_miners)	C++17	0 / 100	15 ms	2516 KiB

miners

#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 (stderr)

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
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 7
• Subtask 7: 0 / 8
• Subtask 8: 0 / 8
• Subtask 9: 0 / 8
• Subtask 10: 0 / 8
• Subtask 11: 0 / 8
• Subtask 12: 0 / 8