| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 611778 | 2022-07-29T07:25:21 Z | 장태환(#8498) | Izlet (COI19_izlet) | C++17 | 1588 ms | 40164 KB |
#include <bits/stdc++.h>
using namespace std;
int N;
int arr[3010][3010];
int uf[3010];
vector<int>link[3010];
int f(int n)
{
return uf[n] == n ? n : uf[n] = f(uf[n]);
}
void u(int n, int m)
{
uf[f(n)] = uf[f(m)];
}
vector<int>r;
void dfs(int n, int p = -1)
{
r.push_back(n);
if (p!=-1)
{
int s = 0;
int e = r.size() - 1;
while (s != e)
{
int m = (s + e) / 2;
if (arr[r[m]][p]!= arr[r[m]][n])
{
e = m;
}
else
{
s = m + 1;
}
}
if (s)
{
u(r[s - 1], n);
}
}
int i;
for (i = 0; i < link[n].size(); i++)
{
if (link[n][i] == p)
continue;
dfs(link[n][i], n);
}
r.pop_back();
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t >> N;
int i,j;
for (i = 0; i < N; i++)
{
uf[i] = i;
for (j = 0; j < N; j++)
{
cin >> arr[i][j];
}
}
vector<pair<int, int>>ans;
for (i = 0; i < N; i++)
{
for (j = 0; j < N; j++)
{
if (arr[i][j] == 1)
{
if (f(i) != f(j))
{
u(i, j);
link[i].push_back(j);
link[j].push_back(i);
ans.push_back({ i + 1,j + 1 });
}
}
}
}
for (i = 0; i < N; i++)
{
for (j = 0; j < N; j++)
{
if (arr[i][j] == 2)
{
if (f(i) != f(j))
{
u(i, j);
link[i].push_back(j);
link[j].push_back(i);
ans.push_back({ i + 1,j + 1 });
}
}
}
}
for (i = 0; i < N; i++)
uf[i] = i;
for (i = 0; i < N; i++)
{
dfs(i);
}
for (i = 0; i < N; i++)
cout << f(i) + 1 << ' ';
cout << '\n';
for (i = 0; i < ans.size(); i++)
{
cout << ans[i].first << ' ' << ans[i].second << '\n';
}
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 468 KB | Output is correct |
| 2 | Correct | 685 ms | 36468 KB | Output is correct |
| 3 | Correct | 693 ms | 36476 KB | Output is correct |
| 4 | Correct | 770 ms | 36416 KB | Output is correct |
| 5 | Correct | 688 ms | 36364 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1097 ms | 36448 KB | Output is correct |
| 2 | Correct | 755 ms | 40072 KB | Output is correct |
| 3 | Correct | 1588 ms | 38928 KB | Output is correct |
| 4 | Correct | 1037 ms | 38944 KB | Output is correct |
| 5 | Correct | 760 ms | 40164 KB | Output is correct |
| 6 | Correct | 922 ms | 37936 KB | Output is correct |
| 7 | Correct | 743 ms | 31808 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 468 KB | Output is correct |
| 2 | Correct | 685 ms | 36468 KB | Output is correct |
| 3 | Correct | 693 ms | 36476 KB | Output is correct |
| 4 | Correct | 770 ms | 36416 KB | Output is correct |
| 5 | Correct | 688 ms | 36364 KB | Output is correct |
| 6 | Correct | 1097 ms | 36448 KB | Output is correct |
| 7 | Correct | 755 ms | 40072 KB | Output is correct |
| 8 | Correct | 1588 ms | 38928 KB | Output is correct |
| 9 | Correct | 1037 ms | 38944 KB | Output is correct |
| 10 | Correct | 760 ms | 40164 KB | Output is correct |
| 11 | Correct | 922 ms | 37936 KB | Output is correct |
| 12 | Correct | 743 ms | 31808 KB | Output is correct |
| 13 | Correct | 1306 ms | 37252 KB | Output is correct |
| 14 | Correct | 909 ms | 37692 KB | Output is correct |
| 15 | Correct | 796 ms | 39776 KB | Output is correct |
| 16 | Correct | 790 ms | 37520 KB | Output is correct |
| 17 | Correct | 883 ms | 37620 KB | Output is correct |
| 18 | Correct | 763 ms | 39768 KB | Output is correct |
| 19 | Correct | 638 ms | 39908 KB | Output is correct |
| 20 | Correct | 874 ms | 39968 KB | Output is correct |
| 21 | Correct | 741 ms | 37236 KB | Output is correct |
| 22 | Correct | 763 ms | 37212 KB | Output is correct |
| 23 | Correct | 878 ms | 37148 KB | Output is correct |
| 24 | Correct | 982 ms | 37632 KB | Output is correct |
| 25 | Correct | 845 ms | 37280 KB | Output is correct |