oj.uz

Submission #144384

# Submission time Handle Problem Language Result Execution time Memory
144384 2019-08-16T19:08:01 Z SamAnd Izlet (COI19_izlet) C++17
100 / 100
 1051 ms 41180 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));
                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

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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 847 ms 36332 KB Output is correct
3 Correct 851 ms 36416 KB Output is correct
4 Correct 854 ms 36260 KB Output is correct
5 Correct 861 ms 36180 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 840 ms 36476 KB Output is correct
2 Correct 865 ms 36136 KB Output is correct
3 Correct 1028 ms 36616 KB Output is correct
4 Correct 1051 ms 36656 KB Output is correct
5 Correct 848 ms 36084 KB Output is correct
6 Correct 870 ms 36220 KB Output is correct
7 Correct 682 ms 30712 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 847 ms 36332 KB Output is correct
3 Correct 851 ms 36416 KB Output is correct
4 Correct 854 ms 36260 KB Output is correct
5 Correct 861 ms 36180 KB Output is correct
6 Correct 840 ms 36476 KB Output is correct
7 Correct 865 ms 36136 KB Output is correct
8 Correct 1028 ms 36616 KB Output is correct
9 Correct 1051 ms 36656 KB Output is correct
10 Correct 848 ms 36084 KB Output is correct
11 Correct 870 ms 36220 KB Output is correct
12 Correct 682 ms 30712 KB Output is correct
13 Correct 864 ms 36028 KB Output is correct
14 Correct 980 ms 40184 KB Output is correct
15 Correct 848 ms 40928 KB Output is correct
16 Correct 942 ms 40068 KB Output is correct
17 Correct 975 ms 39980 KB Output is correct
18 Correct 853 ms 41180 KB Output is correct
19 Correct 871 ms 40956 KB Output is correct
20 Correct 848 ms 40800 KB Output is correct
21 Correct 868 ms 40856 KB Output is correct
22 Correct 890 ms 40720 KB Output is correct
23 Correct 874 ms 40724 KB Output is correct
24 Correct 926 ms 39876 KB Output is correct
25 Correct 864 ms 40664 KB Output is correct