# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1072283 | Abito | The Ties That Guide Us (CEOI23_incursion) | C++17 | 251 ms | 15096 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "incursion.h"
#define pb push_back
#define elif else if
using namespace std;
const int N=5e4+5;
int n;
vector<int> adj1[N],a,b,adj2[N];
bool c[N],d[N];
void geta(int x,int p){
a.pb(x);
for (auto u:adj1[x]){
if (u==p) continue;
geta(u,x);
}return;
}
void getb(int x,int p){
b.pb(x);
for (auto u:adj2[x]){
if (u==p) continue;
getb(u,x);
}return;
}
std::vector<int> mark(std::vector<std::pair<int, int>> F, int safe) {
n=F.size()+1;
if (n==2){
if (safe==1) return {0,1};
return {1,0};
}
for (auto u:F){
adj1[u.first].pb(u.second);
adj1[u.second].pb(u.first);
}
int r;
for (int i=1;i<=n;i++) if (adj1[i].size()==1) r=i;
a.pb(0);
geta(r,0);
for (int i=1;i<=n;i++) c[i]=1;
if (n&1){
int j;
for (int i=1;i<=n;i++) if (a[i]==safe) j=i;
if (j<=n/2+1) for (int i=j;i<=n/2+1;i++) c[a[i]]=0;
else for (int i=n/2+1;i<=j;i++) c[a[i]]=0;
vector<int> v;
for (int i=1;i<=n;i++) v.pb(c[i]);
return v;
}
else{
int j;
for (int i=1;i<=n;i++) if (a[i]==safe) j=i;
if (j==n/2 || j==n/2+1){
c[safe]=0;
}
elif (j<n/2) for (int i=j;i<=n/2+1;i++) c[a[i]]=0;
else for (int i=n/2;i<=j;i++) c[a[i]]=0;
vector<int> v;
for (int i=1;i<=n;i++) v.pb(c[i]);
return v;
}
}
void locate(std::vector<std::pair<int, int>> F, int curr, int t) {
n=F.size()+1;
if (n==2){
if (t==0) return;
if (curr==1) visit(2);
else visit(1);
return;
}
for (auto u:F){
adj2[u.first].pb(u.second);
adj2[u.second].pb(u.first);
}
int r;
for (int i=1;i<=n;i++) if (adj2[i].size()==1) r=i;
b.pb(0);
getb(r,0);
//for (auto u:b) cout<<u<<' ';
//cout<<endl;
if (n&1){
int j;
for (int i=1;i<=n;i++) if (b[i]==curr) j=i;
d[curr]=t;
while (true){
if (d[b[j]]){
if (j<n/2+1){
j++;
d[b[j]]=visit(b[j]);
}
else{
j--;
d[b[j]]=visit(b[j]);
}
}
else{
//return;
if (j==1 || j==n) return;
if (j<n/2+1){
j--;
d[b[j]]=visit(b[j]);
if (d[b[j]]){
j++;
visit(b[j]);
return;
}
continue;
}
elif (j>n/2+1){
j++;
d[b[j]]=visit(b[j]);
if (d[b[j]]){
j--;
visit(b[j]);
return;
}
continue;
}
j--;
d[b[j]]=visit(b[j]);
if (!d[b[j]]) continue;
j++;
d[b[j]]=visit(b[j]);
j++;
d[b[j]]=visit(b[j]);
if (!d[b[j]]) continue;
j--;d[b[j]]=visit(b[j]);
return;
}
}
}
else{
int j;
for (int i=1;i<=n;i++) if (b[i]==curr) j=i;
d[curr]=t;
while (true){
if (d[b[j]]){
if (j<=n/2){
j++;
d[b[j]]=visit(b[j]);
}
else{
j--;
d[b[j]]=visit(b[j]);
}
}
else{
if (j==1 || j==n) return;
if (j<n/2){
j--;
d[b[j]]=visit(b[j]);
if (d[b[j]]){
j++;
visit(b[j]);
return;
}
continue;
}
if (j>n/2+1){
j++;
d[b[j]]=visit(b[j]);
if (d[b[j]]){
j--;
visit(b[j]);
return;
}
continue;
}
if (j==n/2){
j--;
d[b[j]]=visit(b[j]);
j++;
d[b[j]]=visit(b[j]);
j++;
d[b[j]]=visit(b[j]);
j++;
d[b[j]]=visit(b[j]);
if (d[b[n/2+1]]){
j--;
d[b[j]]=visit(b[j]);
j--;
d[b[j]]=visit(b[j]);
return;
}
if (!d[b[n/2+2]]) continue;
j--;
d[b[j]]=visit(b[j]);
j--;
d[b[j]]=visit(b[j]);
j--;
d[b[j]]=visit(b[j]);
continue;
}
else{
j++;
d[b[j]]=visit(b[j]);
j--;
d[b[j]]=visit(b[j]);
j--;
d[b[j]]=visit(b[j]);
j--;
d[b[j]]=visit(b[j]);
if (d[b[n/2]]){
j++;
d[b[j]]=visit(b[j]);
j++;
d[b[j]]=visit(b[j]);
return;
}
if (!d[b[n/2-1]]) continue;
j++;
d[b[j]]=visit(b[j]);
j++;
d[b[j]]=visit(b[j]);
j++;
d[b[j]]=visit(b[j]);
continue;
}
}
}
return;
}
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |