| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 645832 | MadokaMagicaFan | Speedrun (RMI21_speedrun) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using vi = vector<int>;
using pi = pair<int, int>;
#define forn(i,n) for(int i = 0; i < n; ++i)
#define forb(i,b,n) for(int i = b; i < n; ++i)
#define pb push_back
#define sz(v) ((int)((v).size()))
//#define ONPC
void setHintLen(int l);
void setHint(int i, int j, bool b);
int getLength();
bool getHint(int j);
bool goTo(int x);
void
assignHints(int s, int n, vi a, vi b)
{
if (s == 1) {
setHintLen(n);
forb(i,1,n) {
setHint(a[i], b[i], 1);
setHint(b[i], a[i], 1);
}
}
}
vi p;
void dfs1(int x, int n)
{
forb(i,1,n+1) {
if (x == i) continue;
if (i == p[x]) continue;
if (getHint(i)) {
p[i] = x;
goTo(i);
dfs1(i,n);
goTo(x);
}
}
}
void
speedrun(int s, int n, int x) {
if (s == 1) {
p.assign(n+1, -1);
dfs1(x,n);
}
}
#ifdef ONPC
int lg;
int cur;
vector<bool> vis;
int cnt = 0;
int mist = 0;;
vector<vector<bool>> h;
vi a, b;
void setHintLen(int l){
lg = l;
forn(i, sz(h))
h[i].assign(l,0);
}
void setHint(int i, int j, bool b) {
--i, --j;
assert(i < sz(h));
assert(j < lg);
h[i][j] = b;
}
int getLength() {
return lg;
}
bool getHint(int j) {
j--;
assert(j < lg);
return h[cur][j];
}
bool goTo(int x) {
for(int i = 1; i < sz(a); ++i) {
if (a[i] == cur+1 && b[i] == x
|| b[i] == cur+1 && a[i] == x ) {
cur = x - 1;
if (vis[cur] == 0) {
vis[cur] = 1;
++cnt;
}
return 1;
}
}
++mist;
return 0;
}
int32_t
main(int argc, char *argv[])
{
if (argc > 1)
freopen(argv[1], "r", stdin);
ios_base::sync_with_stdio(0); cin.tie(0);
int sub, n, st;
cin >> sub >> n >> st;
h.assign(n,{});
a.assign(n, 0);
b.assign(n, 0);
vis.assign(n,0);
vis[st-1] = 1;
cnt = 1;
for (int i = 1; i < n; ++i) {
cin >> a[i] >> b[i];
}
assignHints(sub, n, a, b);
speedrun(sub, n, st);
cout << cnt << ' ' << mist;
}
#endif