oj.uz

Submission #779412

# Submission time Handle Problem Language Result Execution time Memory
779412 2023-07-11T11:38:18 Z vjudge1 Village (BOI20_village) C++17
12 / 100
 700 ms 1364 KB 
#include <iostream>
#include <vector>
#define INF 2000000000
#define MAX 1000
using namespace std;
///ifstream cin ("c.in");
///ofstream cout ("c.out");
vector <int> graph[MAX + 10];
int dist[MAX + 10][MAX + 10], st[MAX + 10], visited[MAX + 10], n, source, minDist, maxDist, vmin[MAX + 10], vmax[MAX + 10];
void speedy()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
void dfs(int node)
{
    for (auto next : graph[node])
        if (dist[source][next] == 0)
        {
            dist[source][next] = dist[source][node] + 1;
            dfs(next);
        }
}
void solution()
{
    int ok = 1;
    for (int i = 1; i <= n && ok == 1; i++)
        if (st[i] == i)
            ok = 0;
    if (ok == 1)
    {
        int totalDist = 0;
        for (int i = 1; i <= n; i++)
            totalDist = totalDist + dist[i][st[i]];
        if (totalDist < minDist)
        {
            minDist = totalDist;
            for (int i = 1; i <= n; i++)
                vmin[i] = st[i];
        }
        if (totalDist > maxDist)
        {
            maxDist = totalDist;
            for (int i = 1; i <= n; i++)
                vmax[i] = st[i];
        }
    }
}
void bkt(int k)
{
    if (k == n + 1)
        solution();
    else
        for (int i = 1; i <= n; i++)
            if (visited[i] == 0)
            {
                visited[i] = 1;
                st[k] = i;
                bkt(k + 1);
                visited[i] = 0;
            }
}
int main()
{
    speedy();
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    for (int i = 1; i <= n; i++)
    {
        source = i;
        dist[source][source] = 1;
        dfs(i);
        for (int j = 1; j <= n; j++)
            dist[source][j]--;
    }
    minDist = INF;
    maxDist = 0;
    bkt(1);
    cout << minDist << ' ' << maxDist << '\n';
    for (int i = 1; i <= n; i++)
        cout << vmin[i] << ' ';
    cout << '\n';
    for (int i = 1; i <= n; i++)
        cout << vmax[i] << ' ';
    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 352 KB Output is correct
7 Correct 1 ms 352 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 13 ms 340 KB Output is correct
10 Correct 130 ms 380 KB Output is correct
11 Correct 128 ms 384 KB Output is correct
12 Correct 136 ms 380 KB Output is correct
13 Correct 127 ms 392 KB Output is correct
14 Correct 127 ms 348 KB Output is correct
15 Correct 129 ms 388 KB Output is correct
16 Correct 134 ms 384 KB Output is correct
17 Correct 128 ms 396 KB Output is correct

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1069 ms 1364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 352 KB Output is correct
7 Correct 1 ms 352 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 13 ms 340 KB Output is correct
10 Correct 130 ms 380 KB Output is correct
11 Correct 128 ms 384 KB Output is correct
12 Correct 136 ms 380 KB Output is correct
13 Correct 127 ms 392 KB Output is correct
14 Correct 127 ms 348 KB Output is correct
15 Correct 129 ms 388 KB Output is correct
16 Correct 134 ms 384 KB Output is correct
17 Correct 128 ms 396 KB Output is correct
18 Execution timed out 1069 ms 1364 KB Time limit exceeded
19 Halted 0 ms 0 KB -