이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pf push_front
#define fi first
#define se second
const ll mod = 1e9+7, mxn_s1 = 4007, mxn_full = 12e4+7;
ll n, q, cnt[mxn_s1], tl[mxn_full], h[mxn_full], up[mxn_full][20], mx[mxn_full][20], mn[mxn_full][20];
bool connected[mxn_full], lis[mxn_full][20], lds[mxn_full][20];
vector<vector<ll>> v(mxn_s1);
vector<vector<pair<ll,ll>>> g(mxn_full);
void dfs(ll u, ll v)
{
for (pair<ll,ll> i : g[u])
{
if (i.fi != v)
{
h[i.fi] = h[u]+1; up[i.fi][0] = u;
mx[i.fi][0] = mn[i.fi][0] = i.se;
lis[i.fi][0] = lds[i.fi][0] = 1;
dfs(i.fi,u);
}
}
}
void build_lca()
{
for (ll j = 1; j <= 19; j++)
{
for (ll i = 1; i <= n; i++)
{
mx[i][j] = max(mx[i][j-1],mx[up[i][j-1]][j-1]);
mn[i][j] = min(mn[i][j-1],mn[up[i][j-1]][j-1]);
lis[i][j] = (lis[i][j-1] && lis[up[i][j-1]][j-1] && (mx[i][j-1] < mn[up[i][j-1]][j-1]));
lds[i][j] = (lds[i][j-1] && lds[up[i][j-1]][j-1] && (mn[i][j-1] > mx[up[i][j-1]][j-1]));
up[i][j] = up[up[i][j-1]][j-1];
}
}
}
ll lift(ll a, ll b)
{
for (ll i = 19; i >= 0; i--) if (b>>i&1) a = up[a][i];
return a;
}
bool lis_ck(ll a, ll b)
{
bool ck = 1; ll mxx = 0;
for (ll i = 19; i >= 0; i--) if (b>>i&1) {ck &= (lis[a][i] && mn[a][i] > mxx); mxx = mx[a][i]; a = up[a][i];}
return ck;
}
bool lds_ck(ll a, ll b)
{
bool ck = 1; ll mnn = 1e18;
for (ll i = 19; i >= 0; i--) if (b>>i&1) {ck &= (lds[a][i] && mx[a][i] < mnn); mnn = mn[a][i]; a = up[a][i];}
return ck;
}
ll lca(ll a, ll b)
{
if (h[a] != h[b])
{
if (h[a] < h[b]) swap(a,b);
ll k = h[a]-h[b];
for (ll i = __lg(k); i >= 0; i--)
{
if (k >> i & 1) a = up[a][i];
}
}
if (a == b) return a;
for (ll i = 19; i >= 0; i--)
{
if (up[a][i] != up[b][i]) {a = up[a][i]; b = up[b][i];}
}
return up[a][0];
}
ll rmx(ll a, ll b)
{
ll ans = 0;
if (h[a] != h[b])
{
if (h[a] < h[b]) swap(a,b);
ll k = h[a]-h[b];
for (ll i = __lg(k); i >= 0; i--)
{
if (k >> i & 1)
{
ans = max(ans, mx[a][i]);
a = up[a][i];
}
}
}
if (a == b) return ans;
for (ll i = 19; i >= 0; i--)
{
if (up[a][i] != up[b][i])
{
ans = max({ans, mx[a][i], mx[b][i]});
a = up[a][i]; b = up[b][i];
}
}
return max({ans, mx[a][0], mx[b][0]});
}
ll rmn(ll a, ll b)
{
ll ans = 1e18;
if (h[a] != h[b])
{
if (h[a] < h[b]) swap(a,b);
ll k = h[a]-h[b];
for (ll i = __lg(k); i >= 0; i--)
{
if (k >> i & 1)
{
ans = min(ans, mn[a][i]);
a = up[a][i];
}
}
}
if (a == b) return ans;
for (ll i = 19; i >= 0; i--)
{
if (up[a][i] != up[b][i])
{
ans = min({ans, mn[a][i], mn[b][i]});
a = up[a][i]; b = up[b][i];
}
}
return min({ans, mn[a][0], mn[b][0]});
}
struct query {char c; ll l, r;};
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("test.inp","r",stdin); freopen("test.out","w",stdout); freopen("test.err","w",stderr);
cin >> n >> q;
if (n <= 4000)
{
for (ll i = 1; i <= n; i++) {v[i].pb(i); cnt[i]++;}
for (ll i = 1; i < q+n; i++)
{
char c; cin >> c;
if (c == 'C')
{
ll x; cin >> x;
cout << cnt[x] << '\n';
}
else if (c == 'Q')
{
ll x, y; cin >> x >> y;
bool ck = 0;
for (ll j : v[x]) if (j == y) ck = 1;
if (ck) cout << "yes" << '\n';
else cout << "no" << '\n';
}
else
{
ll a, b; cin >> a >> b;
if (v[a].size() > v[b].size()) swap(a,b);
vector<ll> tmp = v[a];
for (ll j : v[b])
{
v[a].pb(j);
cnt[j]++;
}
for (ll j : tmp)
{
v[b].pb(j);
cnt[j]++;
}
}
}
}
else
{
vector<query> qx;
bool ck_s2 = 1, ck_s3 = 1, ck_s4 = 1;
for (ll i = 1; i < q+n; i++)
{
char c; cin >> c;
if (c == 'C')
{
ll x; cin >> x;
qx.pb({c,x,0});
}
else if (c == 'Q')
{
ll x, y; cin >> x >> y;
qx.pb({c,x,y});
}
else
{
ll a, b; cin >> a >> b;
if (a > b) swap(a,b);
qx.pb({c,a,b});
if (a != 1) ck_s2 = 0;
if (b-a != 1) ck_s3 = 0;
if ((a<<1) != b && (a<<1|1) != b) ck_s4 = 0;
}
}
if (0) // ck_s2
{
ll cnt_connected = tl[1] = 1;
for (query i : qx)
{
if (i.c == 'S') tl[i.r] = ++cnt_connected;
else if (i.c == 'C')
{
if (i.l == 1) cout << cnt_connected << '\n';
else cout << cnt_connected-tl[i.l]+1 << '\n';
}
else
{
if (i.l == i.r) cout << "yes" << '\n';
else if (i.l == 1)
{
if (tl[i.r]) cout << "yes" << '\n';
else cout << "no" << '\n';
}
else if (i.r == 1)
{
if (tl[i.l]) cout << "yes" << '\n';
else cout << "no" << '\n';
}
else if (!tl[i.l] || !tl[i.r]) cout << "no" << '\n';
else
{
if (tl[i.l] < tl[i.r]) cout << "no" << '\n';
else cout << "yes" << '\n';
}
}
}
}
else if (0) // ck_s3
{
}
else
{
// cerr << "50%" << '\n';
ll til = 0;
for (query i : qx)
{
til++;
if (i.c == 'S')
{
g[i.l].pb({i.r,til});
g[i.r].pb({i.l,til});
}
}
dfs(1,1); build_lca(); til = 0;
// cerr << lds_ck(3,1);
for (query i : qx)
{
til++;
if (i.c == 'Q')
{
ll l = lca(i.l, i.r);
ll dl = h[i.l]-h[l], dr = h[i.r]-h[l];
// cerr << i.l << ' ' << i.r << ' ' << l << ' ' << dl << ' ' << dr << '\n';
bool liss = lis_ck(i.r, dr), ldss = lds_ck(i.l, dl);
// cerr << liss << ' ' << ldss << '\n';
if (liss && ldss && rmn(i.l,l) > rmx(i.r,l) && rmx(i.l,i.r) <= til) cout << "yes" << '\n';
else cout << "no" << '\n';
}
}
}
}
}
컴파일 시 표준 에러 (stderr) 메시지
servers.cpp: In function 'int main()':
servers.cpp:176:14: warning: variable 'ck_s2' set but not used [-Wunused-but-set-variable]
176 | bool ck_s2 = 1, ck_s3 = 1, ck_s4 = 1;
| ^~~~~
servers.cpp:176:25: warning: variable 'ck_s3' set but not used [-Wunused-but-set-variable]
176 | bool ck_s2 = 1, ck_s3 = 1, ck_s4 = 1;
| ^~~~~
servers.cpp:176:36: warning: variable 'ck_s4' set but not used [-Wunused-but-set-variable]
176 | bool ck_s2 = 1, ck_s3 = 1, ck_s4 = 1;
| ^~~~~
# | 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... |
# | 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... |