Submission #789857

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
789857	2023-07-22 06:18:19	PoonYaPat	Parachute rings (IOI12_rings)	C++14	100 / 100	1792 ms	183624 KiB

rings

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;
int n,p[1000005],r[1000005],lst=-1,deg[1000005];
vector<int> adj[1000005],br;
vector<pii> edge;
set<int> ans;
bool nope=false,vis[1000005];
vector<int> st;
void dfs(int x, int par, int tar) {
  st.push_back(x);
  vis[x]=true;
  if (x==tar) for (auto s : st) br.push_back(s);
  else for (auto s : adj[x]) if (s!=par && !vis[s]) dfs(s,x,tar);
  st.pop_back();
}
int find(int x) {
  while (x!=p[x]) x=p[x];
  return x;
}
void unite(int a, int b) {
  a=find(a); b=find(b);
  if (r[a]<r[b]) swap(a,b);
  p[b]=a;
  if (r[a]==r[b]) ++r[a];
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 20 / 20
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 14 / 14
• Subtask 5: 31 / 31