제출 #144378

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
144378		SamAnd	Izlet (COI19_izlet)	C++17	18 / 100	1090 ms	40696 KiB

izlet

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 18
• Subtask 2: 0 / 25
• Subtask 3: 0 / 57