Submission #236435

#	Time	Username	Problem	Language	Result	Execution time	Memory
236435		Kastanda	Izlet (COI19_izlet)	C++11	0 / 100	959 ms	73236 KiB

izlet

// Pied!
#include<bits/stdc++.h>
using namespace std;
const int N = 3003;
int n, sub, ts, A[N][N], P[N], Par[N], C[N], D[N][N];
bool M[N][N], MR[N];
vector < int > Adj[N];
vector < pair < int , int > > E;
int Find(int v)
{
    return (P[v] < 0 ? v : (P[v] = Find(P[v])));
}
void Root(int v, int p, int root)
{
    for (int u : Adj[v])
        if (u != p)
            D[root][u] = D[root][v] + 1, Root(u, v, root);
}
void DFS(int v, int p)
{
    int best = -1;
    for (int i = 1; i <= n; i ++)
        if (MR[i] && A[v][i] == A[p][i] && (best == -1 || D[v][i] < D[v][best]))
            best = i;
    MR[v] = 1;
    if (best == -1)
        C[v] = ++ ts;
    else
        C[v] = C[best];
    for (int u : Adj[v])
        if (u != p)
            DFS(u, v);
}
int main()
{
    scanf("%d%d", &sub, &n);
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
            scanf("%d", &A[i][j]);
    memset(P, -1, sizeof(P));
    for (int i = 1; i <= n; i ++)
        for (int j = i + 1; j <= n; j ++)
            if (A[i][j] == 1)
            {
                int v = Find(i);
                int u = Find(j);
                if (v == u)
                    continue;
                E.push_back({i, j});
                P[v] = u;
            }
    vector < int > V;
    for (int i = 1; i <= n; i ++)
        if (Find(i) == i)
            V.push_back(i);
    for (int v : V)
        for (int u : V)
            if (v < u && A[v][u] == 2 && Find(v) != Find(u))
            {
                Adj[v].push_back(u);
                Adj[u].push_back(v);
                E.push_back({v, u});
                M[v][u] = M[u][v] = 1;
                P[Find(v)] = Find(u);
            }
    for (int i : V)
        Root(i, 0, i);
    DFS(V[0], 0);
    for (int i = 1; i <= n; i ++)
        if (Find(i) != i)
            C[i] = C[Find(i)];
    for (int i = 1; i <= n; i ++)
        printf("%d ", C[i]);
    printf("\n");
    for (auto X : E)
        printf("%d %d\n", X.first, X.second);
    return 0;
}

Compilation message (stderr)

izlet.cpp: In function 'int main()':
izlet.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &sub, &n);
     ~~~~~^~~~~~~~~~~~~~~~~~
izlet.cpp:39: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: 0 / 18
• Subtask 2: 0 / 25
• Subtask 3: 0 / 57