| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 961070 | 2024-04-11T13:27:15 Z | 12345678 | 가장 긴 여행 (IOI23_longesttrip) | C++17 | 841 ms | 2420 KB |
#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;
const int nx=305;
int qrs[nx][nx], vs[nx], m, cnt, u, v, l[nx], r[nx], st, ed, p;
vector<int> d[nx];
int query(int i, int j)
{
if (i>j) swap(i, j);
return qrs[i][j];
}
void dfs(int u)
{
vs[u]=1;
cnt++;
for (auto v:d[u]) if (!vs[v]) dfs(v);
}
std::vector<int> longest_trip(int N, int D)
{
for (int i=0; i<N; i++) d[i].clear(), vs[i]=0;
for (int i=0; i<N; i++) for (int j=i+1; j<N; j++) qrs[i][j]=are_connected(vector<int> {i}, vector<int> {j});
for (int i=0; i<N; i++) for (int j=0; j<N; j++) if (query(i, j)) d[i].push_back(j);
cnt=0;
dfs(0);
vector<int> res;
if (cnt!=N)
{
if (cnt>=N-cnt) m=1;
else m=0;
for (int i=0; i<N; i++)
{
if (vs[i]&&m) res.push_back(i);
if (!vs[i]&&!m) res.push_back(i);
}
return res;
}
st=ed=0;
queue<pair<int, int>> q;
q.push({0, 0});
for (int i=0; i<N;i ++) vs[i]=0;
vs[0]=1;
while (!q.empty())
{
auto [u, p]=q.front();
if (u!=0)
{
if (query(u, st)) r[u]=st, l[st]=u, st=u;
else if (query(u, ed)) r[ed]=u, l[u]=ed, ed=u;
else
{
r[ed]=st;
l[st]=ed;
st=u;
ed=l[p];
r[u]=p;
l[p]=u;
}
}
q.pop();
for (auto v:d[u]) if (!vs[v]) vs[v]=1, q.push({v, u});
}
while (st!=ed) res.push_back(st), st=r[st];
res.push_back(ed);
return res;
}
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 344 KB | Output is correct |
| 2 | Correct | 195 ms | 1580 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 7 ms | 344 KB | Output is correct |
| 2 | Correct | 23 ms | 344 KB | Output is correct |
| 3 | Correct | 138 ms | 972 KB | Output is correct |
| 4 | Correct | 368 ms | 1244 KB | Output is correct |
| 5 | Correct | 751 ms | 1472 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 8 ms | 344 KB | Output is correct |
| 2 | Correct | 26 ms | 344 KB | Output is correct |
| 3 | Correct | 123 ms | 1112 KB | Output is correct |
| 4 | Correct | 341 ms | 1308 KB | Output is correct |
| 5 | Correct | 688 ms | 1468 KB | Output is correct |
| 6 | Correct | 9 ms | 344 KB | Output is correct |
| 7 | Correct | 27 ms | 344 KB | Output is correct |
| 8 | Correct | 126 ms | 996 KB | Output is correct |
| 9 | Correct | 267 ms | 1016 KB | Output is correct |
| 10 | Correct | 705 ms | 1164 KB | Output is correct |
| 11 | Correct | 732 ms | 1708 KB | Output is correct |
| 12 | Correct | 763 ms | 1896 KB | Output is correct |
| 13 | Correct | 713 ms | 2156 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 7 ms | 344 KB | Output is correct |
| 2 | Correct | 26 ms | 344 KB | Output is correct |
| 3 | Correct | 141 ms | 1116 KB | Output is correct |
| 4 | Correct | 331 ms | 1276 KB | Output is correct |
| 5 | Correct | 686 ms | 1724 KB | Output is correct |
| 6 | Correct | 7 ms | 344 KB | Output is correct |
| 7 | Correct | 29 ms | 344 KB | Output is correct |
| 8 | Correct | 127 ms | 872 KB | Output is correct |
| 9 | Correct | 274 ms | 972 KB | Output is correct |
| 10 | Correct | 687 ms | 1588 KB | Output is correct |
| 11 | Correct | 682 ms | 1196 KB | Output is correct |
| 12 | Correct | 784 ms | 1684 KB | Output is correct |
| 13 | Correct | 736 ms | 1856 KB | Output is correct |
| 14 | Correct | 8 ms | 344 KB | Output is correct |
| 15 | Correct | 12 ms | 344 KB | Output is correct |
| 16 | Correct | 37 ms | 340 KB | Output is correct |
| 17 | Correct | 92 ms | 600 KB | Output is correct |
| 18 | Correct | 130 ms | 1016 KB | Output is correct |
| 19 | Correct | 269 ms | 864 KB | Output is correct |
| 20 | Correct | 266 ms | 972 KB | Output is correct |
| 21 | Correct | 760 ms | 1896 KB | Output is correct |
| 22 | Correct | 771 ms | 2420 KB | Output is correct |
| 23 | Correct | 717 ms | 1700 KB | Output is correct |
| 24 | Correct | 726 ms | 1892 KB | Output is correct |
| 25 | Correct | 11 ms | 344 KB | Output is correct |
| 26 | Correct | 9 ms | 344 KB | Output is correct |
| 27 | Correct | 34 ms | 600 KB | Output is correct |
| 28 | Correct | 35 ms | 600 KB | Output is correct |
| 29 | Correct | 25 ms | 344 KB | Output is correct |
| 30 | Correct | 165 ms | 1372 KB | Output is correct |
| 31 | Correct | 169 ms | 1748 KB | Output is correct |
| 32 | Correct | 187 ms | 712 KB | Output is correct |
| 33 | Correct | 275 ms | 864 KB | Output is correct |
| 34 | Correct | 277 ms | 1240 KB | Output is correct |
| 35 | Correct | 268 ms | 1624 KB | Output is correct |
| 36 | Correct | 736 ms | 1912 KB | Output is correct |
| 37 | Correct | 747 ms | 1604 KB | Output is correct |
| 38 | Correct | 719 ms | 1560 KB | Output is correct |
| 39 | Correct | 744 ms | 1776 KB | Output is correct |
| 40 | Correct | 699 ms | 1596 KB | Output is correct |
| 41 | Correct | 737 ms | 1640 KB | Output is correct |
| 42 | Correct | 722 ms | 1832 KB | Output is correct |
| 43 | Correct | 736 ms | 1668 KB | Output is correct |
| 44 | Correct | 784 ms | 2184 KB | Output is correct |
| 45 | Correct | 10 ms | 344 KB | Output is correct |
| 46 | Correct | 9 ms | 344 KB | Output is correct |
| 47 | Correct | 26 ms | 344 KB | Output is correct |
| 48 | Correct | 27 ms | 344 KB | Output is correct |
| 49 | Correct | 28 ms | 856 KB | Output is correct |
| 50 | Correct | 162 ms | 1476 KB | Output is correct |
| 51 | Correct | 185 ms | 992 KB | Output is correct |
| 52 | Correct | 182 ms | 1272 KB | Output is correct |
| 53 | Correct | 270 ms | 1260 KB | Output is correct |
| 54 | Correct | 257 ms | 1216 KB | Output is correct |
| 55 | Correct | 249 ms | 1724 KB | Output is correct |
| 56 | Correct | 700 ms | 2204 KB | Output is correct |
| 57 | Correct | 749 ms | 1424 KB | Output is correct |
| 58 | Correct | 781 ms | 1436 KB | Output is correct |
| 59 | Correct | 788 ms | 1264 KB | Output is correct |
| 60 | Correct | 841 ms | 1816 KB | Output is correct |
| 61 | Correct | 801 ms | 1248 KB | Output is correct |
| 62 | Correct | 803 ms | 1676 KB | Output is correct |
| 63 | Correct | 789 ms | 1524 KB | Output is correct |
| 64 | Correct | 762 ms | 1436 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 7 ms | 344 KB | Output is correct |
| 2 | Correct | 28 ms | 852 KB | Output is correct |
| 3 | Partially correct | 135 ms | 856 KB | Output is partially correct |
| 4 | Partially correct | 391 ms | 1776 KB | Output is partially correct |
| 5 | Partially correct | 841 ms | 1712 KB | Output is partially correct |
| 6 | Correct | 9 ms | 596 KB | Output is correct |
| 7 | Correct | 33 ms | 600 KB | Output is correct |
| 8 | Partially correct | 134 ms | 736 KB | Output is partially correct |
| 9 | Partially correct | 281 ms | 1008 KB | Output is partially correct |
| 10 | Partially correct | 758 ms | 2416 KB | Output is partially correct |
| 11 | Partially correct | 737 ms | 2068 KB | Output is partially correct |
| 12 | Partially correct | 753 ms | 1928 KB | Output is partially correct |
| 13 | Partially correct | 723 ms | 2200 KB | Output is partially correct |
| 14 | Correct | 10 ms | 344 KB | Output is correct |
| 15 | Correct | 10 ms | 344 KB | Output is correct |
| 16 | Correct | 43 ms | 856 KB | Output is correct |
| 17 | Partially correct | 97 ms | 852 KB | Output is partially correct |
| 18 | Partially correct | 134 ms | 856 KB | Output is partially correct |
| 19 | Partially correct | 249 ms | 1004 KB | Output is partially correct |
| 20 | Partially correct | 273 ms | 1512 KB | Output is partially correct |
| 21 | Correct | 10 ms | 344 KB | Output is correct |
| 22 | Correct | 8 ms | 344 KB | Output is correct |
| 23 | Correct | 21 ms | 344 KB | Output is correct |
| 24 | Correct | 22 ms | 344 KB | Output is correct |
| 25 | Correct | 20 ms | 344 KB | Output is correct |
| 26 | Partially correct | 186 ms | 996 KB | Output is partially correct |
| 27 | Partially correct | 177 ms | 964 KB | Output is partially correct |
| 28 | Partially correct | 167 ms | 1228 KB | Output is partially correct |
| 29 | Partially correct | 258 ms | 1268 KB | Output is partially correct |
| 30 | Partially correct | 274 ms | 1508 KB | Output is partially correct |
| 31 | Partially correct | 266 ms | 1372 KB | Output is partially correct |
| 32 | Correct | 8 ms | 344 KB | Output is correct |
| 33 | Correct | 9 ms | 596 KB | Output is correct |
| 34 | Correct | 25 ms | 344 KB | Output is correct |
| 35 | Correct | 22 ms | 344 KB | Output is correct |
| 36 | Correct | 21 ms | 344 KB | Output is correct |
| 37 | Partially correct | 143 ms | 1480 KB | Output is partially correct |
| 38 | Partially correct | 187 ms | 1240 KB | Output is partially correct |
| 39 | Partially correct | 171 ms | 1228 KB | Output is partially correct |
| 40 | Partially correct | 255 ms | 1136 KB | Output is partially correct |
| 41 | Partially correct | 287 ms | 1144 KB | Output is partially correct |
| 42 | Partially correct | 274 ms | 1496 KB | Output is partially correct |
| 43 | Partially correct | 712 ms | 2096 KB | Output is partially correct |
| 44 | Partially correct | 769 ms | 2164 KB | Output is partially correct |
| 45 | Partially correct | 739 ms | 1388 KB | Output is partially correct |
| 46 | Partially correct | 740 ms | 2408 KB | Output is partially correct |
| 47 | Partially correct | 756 ms | 1292 KB | Output is partially correct |
| 48 | Partially correct | 718 ms | 1616 KB | Output is partially correct |
| 49 | Partially correct | 737 ms | 1892 KB | Output is partially correct |
| 50 | Partially correct | 713 ms | 1668 KB | Output is partially correct |
| 51 | Partially correct | 730 ms | 1564 KB | Output is partially correct |
| 52 | Partially correct | 722 ms | 1328 KB | Output is partially correct |
| 53 | Partially correct | 724 ms | 1780 KB | Output is partially correct |
| 54 | Partially correct | 733 ms | 1864 KB | Output is partially correct |
| 55 | Partially correct | 708 ms | 1656 KB | Output is partially correct |
| 56 | Partially correct | 712 ms | 2036 KB | Output is partially correct |
| 57 | Partially correct | 738 ms | 1620 KB | Output is partially correct |
| 58 | Partially correct | 696 ms | 1920 KB | Output is partially correct |
| 59 | Partially correct | 722 ms | 1688 KB | Output is partially correct |
| 60 | Partially correct | 698 ms | 1928 KB | Output is partially correct |
| 61 | Partially correct | 705 ms | 1948 KB | Output is partially correct |
| 62 | Partially correct | 725 ms | 1876 KB | Output is partially correct |
| 63 | Partially correct | 734 ms | 1400 KB | Output is partially correct |
| 64 | Partially correct | 740 ms | 1868 KB | Output is partially correct |
| 65 | Partially correct | 704 ms | 1408 KB | Output is partially correct |
| 66 | Partially correct | 735 ms | 1700 KB | Output is partially correct |
| 67 | Partially correct | 707 ms | 1664 KB | Output is partially correct |
| 68 | Partially correct | 731 ms | 1412 KB | Output is partially correct |
| 69 | Partially correct | 681 ms | 1008 KB | Output is partially correct |
| 70 | Partially correct | 766 ms | 1648 KB | Output is partially correct |
| 71 | Partially correct | 753 ms | 1840 KB | Output is partially correct |
| 72 | Partially correct | 746 ms | 1992 KB | Output is partially correct |
| 73 | Partially correct | 723 ms | 1760 KB | Output is partially correct |
| 74 | Partially correct | 727 ms | 1484 KB | Output is partially correct |
| 75 | Partially correct | 751 ms | 1696 KB | Output is partially correct |
| 76 | Partially correct | 692 ms | 1648 KB | Output is partially correct |
| 77 | Partially correct | 750 ms | 1892 KB | Output is partially correct |
| 78 | Partially correct | 724 ms | 1680 KB | Output is partially correct |
| 79 | Partially correct | 703 ms | 1288 KB | Output is partially correct |
| 80 | Partially correct | 696 ms | 1852 KB | Output is partially correct |
| 81 | Partially correct | 801 ms | 1860 KB | Output is partially correct |
| 82 | Partially correct | 710 ms | 1800 KB | Output is partially correct |