Submission #157790

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
157790	2019-10-13 00:43:25	imyujin	Izlet (COI19_izlet)	C++17	100 / 100	931 ms	74812 KiB

izlet

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 3010;
int A[MAXN][MAXN];
bool chk[MAXN];
int cnt[MAXN];
int ans[MAXN], cn;
vector<int> ed[MAXN];
int uni[MAXN];
vector<pii> edges;
int guni(int x) { return uni[x] ? uni[x] = guni(uni[x]) : x; }
void unite(int x, int y) { uni[guni(y)] = guni(x); }
int dfs(int v, int x, int p, int k) {
  //printf("dfs(v = %d, x = %d, p = %d, k = %d)\n", v, x, p, k);
  if(++cnt[ans[x]] == 1) k++;
  //printf("k = %d\n", k);
  if(A[v][x] < k) {
    cnt[ans[x]]--;
    return ans[x];
  }
  for(auto a : ed[x]) if(a != p) {
    int t = dfs(v, a, x, k);
    if(t) {
      cnt[ans[x]]--;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 18 / 18
• Subtask 2: 25 / 25
• Subtask 3: 57 / 57