답안 #982388

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
982388	2024-05-14T07:58:29 Z	Marcus	즐거운 행로 (APIO20_fun)	C++17	10 / 100	281 ms	524288 KB

fun

#include "fun.h"
#include <bits/stdc++.h>
using namespace std;
#include <vector>
int n, q;
vector<vector<int>> adj(1e5);
 
std::vector<int> createFunTour(int N, int Q) {
  n=N; q=Q;
  vector<vector<int>> dist(n, vector<int>(n, -1));
  for (int i=0; i<n; i++)
  {
    for (int j=0; j<n; j++)
    {
        dist[i][j] = hoursRequired(i, j);
    }
  }
  vector<vector<pair<int, int>>> dp((1<<n), vector<pair<int, int>> (n));
  for (int i=0; i<n; i++) {dp[1<<i][i] = {1e5+1, -1};}
  for (int s=1; s<(1<<n); s++)
  {
    for (int i=0; i<n; i++)
    {
        if (!(s & (1<<i))) continue;
        for (int j=0; j<n; j++)
        {
            if (!(s & (1<<j)) || i == j) continue;
            int prev = (s^(1<<i));
            if (dp[prev][j].first != 0 && dist[i][j] <= dp[prev][j].first) 
            {
                if (dp[s][i].first < dist[i][j]) {dp[s][i] = {dist[i][j], j};}
            }
        }
    }
  }
  vector<int> answer;
  int s = (1<<n)-1;
  pair<int, int> chain;
  for (int i=0; i<n; i++) {if (dp[s][i].first) {chain = dp[s][i]; answer.push_back(i); break;}}
  while (s)
  {
    s = (s^(1<<(answer.back())));
    if (chain.second != -1) answer.push_back(chain.second);
    chain = dp[s][chain.second];
  }
  reverse(answer.begin(), answer.end());
  return answer;
}

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2796 KB	Output is correct
2	Correct	1 ms	2648 KB	Output is correct
3	Correct	1 ms	2652 KB	Output is correct
4	Correct	2 ms	2652 KB	Output is correct
5	Correct	3 ms	2652 KB	Output is correct
6	Correct	14 ms	5212 KB	Output is correct
7	Correct	27 ms	7512 KB	Output is correct
8	Correct	56 ms	13552 KB	Output is correct
9	Correct	128 ms	24152 KB	Output is correct
10	Correct	2 ms	3060 KB	Output is correct
11	Correct	5 ms	3164 KB	Output is correct
12	Correct	115 ms	24320 KB	Output is correct
13	Correct	107 ms	24408 KB	Output is correct
14	Correct	1 ms	2648 KB	Output is correct
15	Correct	125 ms	24320 KB	Output is correct
16	Correct	120 ms	24328 KB	Output is correct
17	Correct	16 ms	5240 KB	Output is correct
18	Correct	28 ms	7624 KB	Output is correct
19	Correct	70 ms	13548 KB	Output is correct
20	Correct	128 ms	24340 KB	Output is correct

Subtask #2

0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2796 KB	Output is correct
2	Correct	1 ms	2648 KB	Output is correct
3	Correct	1 ms	2652 KB	Output is correct
4	Correct	2 ms	2652 KB	Output is correct
5	Correct	3 ms	2652 KB	Output is correct
6	Correct	14 ms	5212 KB	Output is correct
7	Correct	27 ms	7512 KB	Output is correct
8	Correct	56 ms	13552 KB	Output is correct
9	Correct	128 ms	24152 KB	Output is correct
10	Correct	2 ms	3060 KB	Output is correct
11	Correct	5 ms	3164 KB	Output is correct
12	Correct	115 ms	24320 KB	Output is correct
13	Correct	107 ms	24408 KB	Output is correct
14	Correct	1 ms	2648 KB	Output is correct
15	Correct	125 ms	24320 KB	Output is correct
16	Correct	120 ms	24328 KB	Output is correct
17	Correct	16 ms	5240 KB	Output is correct
18	Correct	28 ms	7624 KB	Output is correct
19	Correct	70 ms	13548 KB	Output is correct
20	Correct	128 ms	24340 KB	Output is correct
21	Correct	263 ms	49748 KB	Output is correct
22	Runtime error	266 ms	524288 KB	Execution killed with signal 9
23	Halted	0 ms	0 KB	-

Subtask #3

0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2648 KB	Output is correct
2	Correct	1 ms	2652 KB	Output is correct
3	Correct	2 ms	2652 KB	Output is correct
4	Correct	3 ms	2652 KB	Output is correct
5	Correct	14 ms	5212 KB	Output is correct
6	Correct	27 ms	7512 KB	Output is correct
7	Correct	56 ms	13552 KB	Output is correct
8	Correct	128 ms	24152 KB	Output is correct
9	Correct	263 ms	49748 KB	Output is correct
10	Runtime error	266 ms	524288 KB	Execution killed with signal 9
11	Halted	0 ms	0 KB	-

Subtask #4

0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2648 KB	Output is correct
2	Correct	1 ms	2652 KB	Output is correct
3	Correct	2 ms	3060 KB	Output is correct
4	Correct	5 ms	3164 KB	Output is correct
5	Correct	115 ms	24320 KB	Output is correct
6	Correct	107 ms	24408 KB	Output is correct
7	Correct	256 ms	50256 KB	Output is correct
8	Runtime error	281 ms	524288 KB	Execution killed with signal 9
9	Halted	0 ms	0 KB	-

Subtask #5

0 / 34.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2796 KB	Output is correct
2	Correct	1 ms	2648 KB	Output is correct
3	Correct	1 ms	2652 KB	Output is correct
4	Correct	2 ms	2652 KB	Output is correct
5	Correct	3 ms	2652 KB	Output is correct
6	Correct	14 ms	5212 KB	Output is correct
7	Correct	27 ms	7512 KB	Output is correct
8	Correct	56 ms	13552 KB	Output is correct
9	Correct	128 ms	24152 KB	Output is correct
10	Correct	2 ms	3060 KB	Output is correct
11	Correct	5 ms	3164 KB	Output is correct
12	Correct	115 ms	24320 KB	Output is correct
13	Correct	107 ms	24408 KB	Output is correct
14	Correct	1 ms	2648 KB	Output is correct
15	Correct	125 ms	24320 KB	Output is correct
16	Correct	120 ms	24328 KB	Output is correct
17	Correct	16 ms	5240 KB	Output is correct
18	Correct	28 ms	7624 KB	Output is correct
19	Correct	70 ms	13548 KB	Output is correct
20	Correct	128 ms	24340 KB	Output is correct
21	Correct	263 ms	49748 KB	Output is correct
22	Runtime error	266 ms	524288 KB	Execution killed with signal 9
23	Halted	0 ms	0 KB	-