oj.uz

Submission #236440

# Submission time Handle Problem Language Result Execution time Memory
236440 2020-06-02T08:30:31 Z Kastanda Izlet (COI19_izlet) C++11
100 / 100
 1560 ms 109048 KB 
// 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

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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 1136 ms 88800 KB Output is correct
3 Correct 1147 ms 88824 KB Output is correct
4 Correct 1184 ms 88704 KB Output is correct
5 Correct 1145 ms 88568 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1099 ms 71416 KB Output is correct
2 Correct 1204 ms 88824 KB Output is correct
3 Correct 1560 ms 109048 KB Output is correct
4 Correct 1415 ms 86848 KB Output is correct
5 Correct 1181 ms 88952 KB Output is correct
6 Correct 1318 ms 95904 KB Output is correct
7 Correct 989 ms 79048 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 1136 ms 88800 KB Output is correct
3 Correct 1147 ms 88824 KB Output is correct
4 Correct 1184 ms 88704 KB Output is correct
5 Correct 1145 ms 88568 KB Output is correct
6 Correct 1099 ms 71416 KB Output is correct
7 Correct 1204 ms 88824 KB Output is correct
8 Correct 1560 ms 109048 KB Output is correct
9 Correct 1415 ms 86848 KB Output is correct
10 Correct 1181 ms 88952 KB Output is correct
11 Correct 1318 ms 95904 KB Output is correct
12 Correct 989 ms 79048 KB Output is correct
13 Correct 1302 ms 89616 KB Output is correct
14 Correct 1443 ms 96632 KB Output is correct
15 Correct 1148 ms 88696 KB Output is correct
16 Correct 1311 ms 93304 KB Output is correct
17 Correct 1329 ms 95220 KB Output is correct
18 Correct 1157 ms 88952 KB Output is correct
19 Correct 1164 ms 88692 KB Output is correct
20 Correct 1217 ms 88924 KB Output is correct
21 Correct 1227 ms 89404 KB Output is correct
22 Correct 1224 ms 89032 KB Output is correct
23 Correct 1294 ms 89460 KB Output is correct
24 Correct 1399 ms 95828 KB Output is correct
25 Correct 1190 ms 88892 KB Output is correct