Submission #144384

#	Time	Username	Problem	Language	Result	Execution time	Memory
144384		SamAnd	Izlet (COI19_izlet)	C++17	100 / 100	1051 ms	41180 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));
                g[fi(h)].push_back(x);
                dfs(fi(h));
            }
        }
    }
}

int z;
int ans[N];

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

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

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), 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]);
    }
    set<pair<int, int> > s;
    for (int x = 1; x <= n; ++x)
    {
        for (int i = 0; i < g[x].size(); ++i)
        {
            int h = g[x][i];
            if (s.find(m_p(h, x)) != s.end())
                continue;
            s.insert(m_p(x, h));
            printf("%d %d\n", x, h);
        }
    }
    return 0;
}

Compilation message (stderr)

izlet.cpp: In function 'int dfs2(int, int, int, int)':
izlet.cpp:54: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, int)':
izlet.cpp:75: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:113:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 1; j < v[i].size(); ++j)
                         ~~^~~~~~~~~~~~~
izlet.cpp:119:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < g[x].size(); ++i)
                         ~~^~~~~~~~~~~~~
izlet.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
izlet.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
izlet.cpp:92: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: 25 / 25
• Subtask 3: 57 / 57