oj.uz

답안 #44761

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
44761 2018-04-06T05:43:37 Z RayaBurong25_1 Pipes (CEOI15_pipes) C++17
0 / 100
 5000 ms 23380 KB 
#include <stdio.h>
#include <vector>
#include <queue>
#include <cstdlib>
#include <string.h>
std::vector<int> AdjList[100005];
int Vis[100005];
int p[100005];
int H[100005];
int* Pa;
int mark[100005];
int N;
std::vector<std::pair<int, int> > Q;
int UF(int u)
{
    return (p[u] == 0)?u:(p[u] = UF(p[u]));
}
void dfs(int u, int pa, int h)
{
    // printf("dfs u%d pa%d h%d\n", u, pa, h);
    Vis[u] = 1;
    H[u] = h;
    *(Pa + u - 1) = pa;
    int i, v, s = AdjList[u].size();
    for (i = 0; i < s; i++)
    {
        v = AdjList[u][i];
        if (v != pa)
            dfs(v, u, h + 1);
    }
}
int lgN;
int lca(int u, int v)
{
    if (H[v] > H[u])
        return lca(v, u);
    int i;
    if (H[u] > H[v])
    {
        for (i = lgN - 1; i >= 0; i--)
            if (H[*(Pa + N*i + u - 1)] > H[v])
                u = *(Pa + N*i + u - 1);
        u = *(Pa + u - 1);
    }
    if (u == v)
        return u;
    for (i = lgN - 1; i >= 0; i--)
    {
        if (*(Pa + N*i + u - 1) != *(Pa + N*i + v - 1))
        {
            u = *(Pa + N*i + u - 1);
            v = *(Pa + N*i + v - 1);
        }
    }
    return *(Pa + u - 1);
}
void dfsMark(int u, int pa)
{
    int i, v, s = AdjList[u].size();
    Vis[u] = 0;
    for (i = 0; i < s; i++)
    {
        v = AdjList[u][i];
        if (v != pa)
        {
            dfsMark(v, u);
            mark[u] += mark[v];
        }
    }
}
int main()
{
    int M;
    scanf("%d %d", &N, &M);
    for (lgN = 0; (1 << lgN) <= N; lgN++);
    int i, j, u, v, pu, pv;
    int cnt = 0;
    for (i = 0; i < M && cnt < N - 1; i++)
    {
        scanf("%d %d", &u, &v);
        if ((pu = UF(u)) != (pv = UF(v)))
        {
            AdjList[u].push_back(v);
            AdjList[v].push_back(u);
            p[pu] = pv;
            cnt++;
        }
        else
        {
            Q.push_back({u, v});
        }
    }
    Pa = (int*) malloc(sizeof(int[lgN][N]));
    // memset(Pa, lgN*N, 0);
    // printf("hello\n");
    for (i = 1; i <= N; i++)
        if (!Vis[i])
            dfs(i, 0, 0);
    for (j = 1; j < lgN; j++)
    {
        for (i = 1; i <= N; i++)
        {
            u = *(Pa + (j - 1)*N + i - 1);
            // printf("j%d i%d u%d\n", j, i, u);
            if (u != 0)
            {
                *(Pa + j*N + i - 1) = *(Pa + (j - 1)*N + u - 1);
            }
            else
            {
                *(Pa + j*N + i - 1) = 0;
            }
            // printf("%d\n", *(Pa + j*N + i - 1));
            // Pa[j][i] = Pa[j - 1][Pa[j - 1][i]];
        }
    }
    // printf("hello\n");
    for (j = 0; j < Q.size(); j++)
    {
        u = Q[j].first;
        v = Q[j].second;
        // printf("Q u%d v%d\n", u, v);
        mark[u]++;
        mark[v]++;
        // printf("lca %d\n", lca(u, v));
        mark[lca(u, v)] -= 2;
    }
    Q.~vector<std::pair<int, int> >();
    for (; i < M; i++)
    {
        scanf("%d %d", &u, &v);
        // printf("# u%d v%d\n", u, v);
        mark[u]++;
        mark[v]++;
        // printf("lca %d\n", lca(u, v));
        mark[lca(u, v)] -= 2;
    }
    for (i = 1; i <= N; i++)
        if (Vis[i])
            dfsMark(i, 0);
    for (i = 1; i <= N; i++)
    {
        // printf("mark[%d] = %d\n", i, mark[i]);
        if (mark[i] == 0 && *(Pa + i - 1) != 0)
            printf("%d %d\n", i, *(Pa + i - 1));
    }
}

Compilation message

pipes.cpp: In function 'int main()':
pipes.cpp:118:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (j = 0; j < Q.size(); j++)
                 ~~^~~~~~~~~~
pipes.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~~
pipes.cpp:131:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 5220 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 15 ms 6132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 218 ms 6136 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 575 ms 7288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1154 ms 10092 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2562 ms 21056 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4211 ms 23380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5092 ms 18480 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5098 ms 18316 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5095 ms 17216 KB Time limit exceeded
2 Halted 0 ms 0 KB -