Submission #236440

#	Time	Username	Problem	Language	Result	Execution time	Memory
236440		Kastanda	Izlet (COI19_izlet)	C++11	100 / 100	1560 ms	109048 KiB

izlet

// Pied!
#include<bits/stdc++.h>
using namespace std;
const int N = 3003;
int n, sub, ts, A[N][N], F[N], C[N], D[N][N];
bool M[N][N], MR[N];
vector < int > Adj[N];
vector < pair < int , int > > E;
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(F, 63, sizeof(F));
    F[1] = 0;
    for (int __ = 1; __ <= n; __ ++)
    {
        int v = 0;
        for (int i = 1; i <= n; i ++)
            if (!MR[i] && (!v || F[i] < F[v]))
                v = i;
        bool ff = 0;
        for (int i = 1; i <= n && !ff; i ++)
            if (MR[i] && A[i][v] == F[v])
                E.push_back({i, v}),
                Adj[i].push_back(v),
                Adj[v].push_back(i),
                ff = 1;
        MR[v] = 1;
        for (int i = 1; i <= n; i ++)
            if (!MR[i] && A[v][i] < F[i])
                F[i] = A[v][i];
    }
    memset(MR, 0, sizeof(MR));
    for (int i = 1; i <= n; i ++)
        Root(i, 0, i);
    DFS(1, 0);
    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:32: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:35: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