oj.uz

답안 #290649

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
290649 2020-09-04T09:11:10 Z Kastanda 즐거운 행로 (APIO20_fun) C++11
10 / 100
 4 ms 5248 KB 
// M
#include<bits/stdc++.h>
#include "fun.h"
using namespace std;
const int N = 100005;
int n, Centroid, H[N];
map < int , int > MP[N];
inline int GetDist(int i, int j)
{
        if (i == j)
                return 0;
        if (MP[i][j])
                return MP[i][j];
        MP[i][j] = MP[j][i] = hoursRequired(i, j);
        return MP[i][j];
}

vector < int > createFunTour(int _n, int Q)
{
        n = _n;
        Centroid = 0;
        for (int i = 1; i < n; i ++)
                if (attractionsBehind(Centroid, i) * 2 > n)
                        Centroid = i;

        vector < int > Ch, vec[3];
        for (int i = 0; i < n; i ++)
                H[i] = GetDist(Centroid, i);
        for (int i = 0; i < n; i ++)
                if (H[i] == 1)
                        Ch.push_back(i);
        assert((int)Ch.size() <= 3);
        int k = (int)Ch.size();
        for (int i = 0; i < n; i ++)
                if (H[i] >= 1)
                {
                        int j = 0;
                        while (j + 1 < k && H[i] != GetDist(Ch[j], i) + 1)
                                j ++;
                        vec[j].push_back(i);
                }
        for (int i = 0; i < k; i ++)
                sort(vec[i].begin(), vec[i].end(), [&](int v, int u){return H[v] < H[u];});

        int last = -1;
        vector < int > P;
        while (true)
        {
                int j = -1;
                for (int i = 0; i < k; i ++)
                        if (i != last && (j == -1 || vec[i].size() > vec[j].size()))
                                j = i;
                if (j == -1 || !vec[j].size())
                        break;
                P.push_back(vec[j].back());
                vec[j].pop_back();
                last = j;
        }
        P.push_back(Centroid);
        int Cnt = 0;
        for (int i = 0; i < k; i ++)
                if (vec[i].size())
                        Cnt ++;
        assert(Cnt <= 1);
        if (!Cnt)
                return P;
        int j = 0;
        while (!vec[j].size())
                j ++;
        for (int i = 0; i < (int)vec[j].size(); i ++)
        {
                P.push_back(vec[j].back());
                vec[j].pop_back();
                if (i < (int)vec[j].size())
                        P.push_back(vec[j][i]);
        }
        return P;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 3 ms 4992 KB Output is correct
6 Correct 3 ms 4992 KB Output is correct
7 Correct 3 ms 4992 KB Output is correct
8 Correct 3 ms 4992 KB Output is correct
9 Correct 3 ms 4992 KB Output is correct
10 Correct 3 ms 4992 KB Output is correct
11 Correct 3 ms 4992 KB Output is correct
12 Correct 4 ms 4992 KB Output is correct
13 Correct 3 ms 4992 KB Output is correct
14 Correct 3 ms 4992 KB Output is correct
15 Correct 3 ms 4992 KB Output is correct
16 Correct 3 ms 4992 KB Output is correct
17 Correct 3 ms 4992 KB Output is correct
18 Correct 3 ms 4992 KB Output is correct
19 Correct 3 ms 4992 KB Output is correct
20 Correct 3 ms 4992 KB Output is correct

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 3 ms 4992 KB Output is correct
6 Correct 3 ms 4992 KB Output is correct
7 Correct 3 ms 4992 KB Output is correct
8 Correct 3 ms 4992 KB Output is correct
9 Correct 3 ms 4992 KB Output is correct
10 Correct 3 ms 4992 KB Output is correct
11 Correct 3 ms 4992 KB Output is correct
12 Correct 4 ms 4992 KB Output is correct
13 Correct 3 ms 4992 KB Output is correct
14 Correct 3 ms 4992 KB Output is correct
15 Correct 3 ms 4992 KB Output is correct
16 Correct 3 ms 4992 KB Output is correct
17 Correct 3 ms 4992 KB Output is correct
18 Correct 3 ms 4992 KB Output is correct
19 Correct 3 ms 4992 KB Output is correct
20 Correct 3 ms 4992 KB Output is correct
21 Correct 3 ms 4992 KB Output is correct
22 Correct 4 ms 4992 KB Output is correct
23 Correct 4 ms 4992 KB Output is correct
24 Incorrect 4 ms 5120 KB Tour is not fun
25 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 3 ms 4992 KB Output is correct
6 Correct 3 ms 4992 KB Output is correct
7 Correct 3 ms 4992 KB Output is correct
8 Correct 3 ms 4992 KB Output is correct
9 Correct 3 ms 4992 KB Output is correct
10 Correct 4 ms 4992 KB Output is correct
11 Correct 4 ms 4992 KB Output is correct
12 Incorrect 4 ms 5120 KB Tour is not fun
13 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Correct 3 ms 4992 KB Output is correct
7 Correct 3 ms 4992 KB Output is correct
8 Incorrect 4 ms 5248 KB Tour is not fun
9 Halted 0 ms 0 KB -

Subtask #5
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 3 ms 4992 KB Output is correct
4 Correct 3 ms 4992 KB Output is correct
5 Correct 3 ms 4992 KB Output is correct
6 Correct 3 ms 4992 KB Output is correct
7 Correct 3 ms 4992 KB Output is correct
8 Correct 3 ms 4992 KB Output is correct
9 Correct 3 ms 4992 KB Output is correct
10 Correct 3 ms 4992 KB Output is correct
11 Correct 3 ms 4992 KB Output is correct
12 Correct 4 ms 4992 KB Output is correct
13 Correct 3 ms 4992 KB Output is correct
14 Correct 3 ms 4992 KB Output is correct
15 Correct 3 ms 4992 KB Output is correct
16 Correct 3 ms 4992 KB Output is correct
17 Correct 3 ms 4992 KB Output is correct
18 Correct 3 ms 4992 KB Output is correct
19 Correct 3 ms 4992 KB Output is correct
20 Correct 3 ms 4992 KB Output is correct
21 Correct 3 ms 4992 KB Output is correct
22 Correct 4 ms 4992 KB Output is correct
23 Correct 4 ms 4992 KB Output is correct
24 Incorrect 4 ms 5120 KB Tour is not fun
25 Halted 0 ms 0 KB -