이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define m_p make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int N = 400005;
const int m = 28;
const ll INF = 1000000009000000009;
int n;
vector<int> S, P, W, L;
vector<int> t[N];
ll st[m][N];
int ut[m][N];
void dfst(int x, int j)
{
if (x == n || S[x] >= (1 << j))
{
st[j][x] = 0;
ut[j][x] = x;
}
for (int i = 0; i < sz(t[x]); ++i)
{
int h = t[x][i];
ut[j][h] = ut[j][x];
st[j][h] = st[j][x] + S[h];
dfst(h, j);
}
}
pair<int, ll> u[m][N];
//////////////////////////////////////////////////////////////
vector<vector<int> > vv;
int c[N];
bool dfsc(int x, int j)
{
c[x] = 1;
int h = u[j][x].fi;
if (!c[h])
{
if (dfsc(h, j))
{
c[x] = 2;
return true;
}
}
else if (c[h] == 1)
{
vector<int> v;
while (h != x)
{
v.push_back(h);
h = u[j][h].fi;
}
v.push_back(x);
vv.push_back(v);
c[x] = 2;
return true;
}
c[x] = 2;
return false;
}
int minc[m][N];
ll sc[m][N];
vector<pair<int, ll> > g[N];
int q[N];
ll d[m][N];
void dfs0(int x, int j)
{
q[x] = 1;
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i].fi;
d[j][h] = d[j][x] + g[x][i].se;
dfs0(h, j);
q[x] += q[h];
}
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i].fi;
if (q[h] > q[g[x][0].fi])
{
swap(g[x][i], g[x][0]);
}
}
}
int tin[m][N], tout[m][N], ti[m], rtin[m][N];
int f[m][N];
int p0[m][N];
void dfs1(int x, int j)
{
tin[j][x] = ++ti[j];
rtin[j][tin[j][x]] = x;
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i].fi;
p0[j][h] = x;
if (i == 0)
f[j][h] = f[j][x];
else
f[j][h] = h;
dfs1(h, j);
}
tout[j][x] = ti[j];
}
ll minu[m][N * 4];
void ubd(int j, int tl, int tr, int x, ll y, int pos)
{
if (tl == tr)
{
minu[j][pos] = y;
return;
}
int m = (tl + tr) / 2;
if (x <= m)
ubd(j, tl, m, x, y, pos * 2);
else
ubd(j, m + 1, tr, x, y, pos * 2 + 1);
minu[j][pos] = min(minu[j][pos * 2], minu[j][pos * 2 + 1]);
}
int qry(int j, int tl, int tr, int l, int r, ll y, int pos)
{
if (l > r)
return ti[j] + 1;
if (tl == l && tr == r)
{
if (minu[j][pos] > y)
return ti[j] + 1;
if (tl == tr)
return tl;
}
int m = (tl + tr) / 2;
int ans = qry(j, m + 1, tr, max(m + 1, l), r, y, pos * 2 + 1);
if (ans <= ti[j])
return ans;
return qry(j, tl, m, l, min(m, r), y, pos * 2);
}
ll qry(int j, int tl, int tr, int l, int r, int pos)
{
if (l > r)
return INF;
if (tl == l && tr == r)
return minu[j][pos];
int m = (tl + tr) / 2;
return min(qry(j, tl, m, l, min(m, r), pos * 2),
qry(j, m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
}
ll minf[m][N];
int qry(int j, int x, ll y)
{
while (1)
{
if (minf[j][x] <= y)
{
int ans = qry(j, 1, ti[j], tin[j][f[j][x]], tin[j][x], y, 1);
assert(ans <= ti[j]);
return rtin[j][ans];
}
x = f[j][x];
if (d[j][x] == 0)
return x;
x = p0[j][x];
}
}
void init(int NN, std::vector<int> SS, std::vector<int> PP, std::vector<int> WW, std::vector<int> LL) {
n = NN;
S = SS;
P = PP;
W = WW;
L = LL;
for (int i = 0; i < n; ++i)
{
t[W[i]].push_back(i);
}
for (int j = 0; j < m; ++j)
{
vv.clear();
for (int i = 0; i <= n; ++i)
{
g[i].clear();
c[i] = 0;
}
dfst(n, j);
for (int x = 0; x < n; ++x)
{
if (S[x] >= (1 << j))
{
u[j][x] = m_p(ut[j][L[x]], P[x] + st[j][L[x]]);
}
}
u[j][n] = m_p(n, 0);
////////////////////////////////////////////////////////////////////////////
for (int x = 0; x <= n; ++x)
{
if (x == n || S[x] >= (1 << j))
{
if (!c[x])
{
dfsc(x, j);
}
}
}
for (int x = 0; x <= n; ++x)
{
c[x] = 0;
}
for (int i = 0; i < sz(vv); ++i)
{
c[vv[i][0]] = 1;
if (vv[i][0] == n)
{
assert(sz(vv[i]) == 1);
continue;
}
minc[j][vv[i][0]] = S[vv[i][0]];
for (int k = 0; k < sz(vv[i]); ++k)
{
minc[j][vv[i][0]] = min(minc[j][vv[i][0]], S[vv[i][k]]);
sc[j][vv[i][0]] += u[j][vv[i][k]].se;
}
}
for (int x = 0; x <= n; ++x)
{
if (x == n || S[x] >= (1 << j))
{
if (!c[x])
g[u[j][x].fi].push_back(m_p(x, u[j][x].se));
}
}
for (int x = 0; x <= n; ++x)
{
if (c[x])
{
dfs0(x, j);
f[j][x] = x;
dfs1(x, j);
}
}
for (int x = 0; x <= n; ++x)
{
if (x == n || S[x] >= (1 << j))
{
if (x != n)
ubd(j, 1, ti[j], tin[j][x], d[j][x] + S[x], 1);
else
{
assert(d[j][x] == 0);
ubd(j, 1, ti[j], tin[j][x], d[j][x], 1);
}
}
}
for (int x = 0; x <= n; ++x)
{
if (x == n || S[x] >= (1 << j))
{
minf[j][x] = qry(j, 1, ti[j], tin[j][f[j][x]], tin[j][x], 1);
}
}
}
}
long long simulate(int x, int Z) {
ll z = Z;
while (x != n)
{
for (int j = m - 1; j >= 0; --j)
{
if (z >= (1 << j))
{
z += st[j][x];
x = ut[j][x];
/*while (x != n && z < S[x])
{
z += u[j][x].se;
x = u[j][x].fi;
}*/
int qq = 0;
while (x != n && z < S[x])
{
++qq;
int p = qry(j, x, z + d[j][x]);
z += d[j][x] - d[j][p];
x = p;
if (x != n && z < S[x])
{
ll q = (minc[j][x] - z);
if (q < 0)
q = 0;
else
q = (q / sc[j][x]);
z += q * sc[j][x];
if (z < S[x])
{
z += u[j][x].se;
x = u[j][x].fi;
}
}
}
assert(qq <= 2);
if (x != n)
{
assert(z >= S[x]);
z += S[x];
x = W[x];
}
break;
}
}
}
return z;
}
/*
3 2
2 6 9
3 1 2
2 2 3
1 0 1
0 1
2 3
*/
컴파일 시 표준 에러 (stderr) 메시지
dungeons.cpp: In function 'void dfs0(int, int)':
dungeons.cpp:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for (int i = 0; i < g[x].size(); ++i)
| ~~^~~~~~~~~~~~~
dungeons.cpp:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for (int i = 0; i < g[x].size(); ++i)
| ~~^~~~~~~~~~~~~
dungeons.cpp: In function 'void dfs1(int, int)':
dungeons.cpp:105:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for (int i = 0; i < g[x].size(); ++i)
| ~~^~~~~~~~~~~~~
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |