| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1065009 | beaconmc | The Ties That Guide Us (CEOI23_incursion) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "incursion.h"
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
using namespace std;
ll sub[50000];
vector<ll> edges[50000];
ll par[50000];
ll visited[50000];
ll depth[50000];
ll unsure[50000];
ll n;
void dfs(ll a, ll p, ll d){
depth[a] = d;
par[a] = p;
sub[a] = 1;
for (auto&i : edges[a]){
if (i != p) dfs(i,a,d+1), sub[a] += sub[i];
}
}
ll centfind(ll a, ll p){
for (auto&i : edges[a]){
if (i!=p && sub[i] > n/2) return centfind(i, a);
}
return a;
}
vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
n = (ll)F.size()+1;
vector<int> ties(n);
FOR(i,0,50000) edges[i].clear(), sub[i] = 0, par[i] = -1, depth[i] = 0;
for (auto&i : F){
edges[i.first].push_back(i.second);
edges[i.second].push_back(i.first);
}
dfs(1, -1, 0);
ll cent = centfind(1, -1);
dfs(cent, -1, 0);
while (safe != -1){
ties[safe-1] = 1;
safe = par[safe];
}
return ties;
}
bool cmp(ll a, ll b){
return sub[a] < sub[b];
}
void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
n = (ll)F.size()+1;
FOR(i,0,50000) edges[i].clear(), sub[i] = 0, par[i] = -1, depth[i] = 0;
for (auto&i : F){
edges[i.first].push_back(i.second);
edges[i.second].push_back(i.first);
}
dfs(1, -1, 0);
ll cent = centfind(1, -1);
dfs(cent, -1, 0);
visited[curr] = 1;
while (t != 1 && curr != cent){
t = visit(par[curr]);
curr = par[curr];
visited[curr] = 1;
}
while (1){
if (t==0 && curr!=cent){
t = visit(par[curr]);
curr = par[curr];
}
reverse(edges[curr].begin(), edges[curr].end());
bool done = false;
for (auto&i : edges[curr]){
if (i==par[curr]) continue;
if (!visited[i]){
visited[i] = true;
t = visit(i);
curr = i;
done = true;
break;
}
}
if (!done){
if (curr != cent && visited[par[curr]] == 0){
t = visit(par[curr]);
visited[par[curr]] = 1;
curr = par[curr];
}else{
return;
}
}
}
}