oj.uz

답안 #144378

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
144378 2019-08-16T18:50:11 Z SamAnd Izlet (COI19_izlet) C++17
18 / 100
 1090 ms 40696 KB 
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N = 3003;

int n;
int a[N][N];

int p[N];
int fi(int x)
{
    if (x == p[x])
        return x;
    return p[x] = fi(p[x]);
}
void kpc(int x, int y)
{
    x = fi(x);
    y = fi(y);
    p[x] = y;
}

vector<int> g[N];

bool c[N];
void dfs(int x)
{
    c[x] = true;
    for (int h = 1; h <= n; ++h)
    {
        if (a[x][h] == 2)
        {
            if (c[fi(h)] == false)
            {
                g[x].push_back(fi(h));
                dfs(fi(h));
            }
        }
    }
}

int z;
int ans[N];

void dfs2(int x, int p, int pp)
{
    if (x != p && a[pp][x] == a[pp][p])
    {
        ans[x] = ans[pp];
        return;
    }
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        dfs2(h, x, pp);
    }
}

void dfs1(int x)
{
    if (ans[x] == 0)
        ans[x] = ++z;
    dfs2(x, x, x);
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        dfs1(h);
    }
}

vector<int> v[N];
int main()
{
    scanf("%d", &n);
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
            scanf("%d", &a[i][j]);
    }
    for (int i = 1; i <= n; ++i)
        p[i] = i;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if (a[i][j] == 1)
                kpc(i, j);
        }
    }
    dfs(fi(1));
    dfs1(fi(1));
    for (int i = 1; i <= n; ++i)
        printf("%d ", ans[fi(i)]);
    printf("\n");
    for (int i = 1; i <= n; ++i)
        v[fi(i)].push_back(i);
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j < v[i].size(); ++j)
            printf("%d %d\n", v[i][j - 1], v[i][j]);
    }
    for (int x = 1; x <= n; ++x)
    {
        for (int i = 0; i < g[x].size(); ++i)
        {
            int h = g[x][i];
            printf("%d %d\n", x, h);
        }
    }
    return 0;
}

Compilation message

izlet.cpp: In function 'void dfs2(int, int, int)':
izlet.cpp:52:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
izlet.cpp: In function 'void dfs1(int)':
izlet.cpp:64:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
izlet.cpp: In function 'int main()':
izlet.cpp:100:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 1; j < v[i].size(); ++j)
                         ~~^~~~~~~~~~~~~
izlet.cpp:105:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < g[x].size(); ++i)
                         ~~^~~~~~~~~~~~~
izlet.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
izlet.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
izlet.cpp:79:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &a[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 806 ms 40696 KB Output is correct
3 Correct 808 ms 40676 KB Output is correct
4 Correct 1090 ms 40376 KB Output is correct
5 Correct 827 ms 40660 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 838 ms 40452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 806 ms 40696 KB Output is correct
3 Correct 808 ms 40676 KB Output is correct
4 Correct 1090 ms 40376 KB Output is correct
5 Correct 827 ms 40660 KB Output is correct
6 Incorrect 838 ms 40452 KB Output isn't correct
7 Halted 0 ms 0 KB -