이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 120005;
vector<pair<int, int> > g[N];
int cnt = 0;
int DP[20][N], isDecreasing[20][N], isIncreasing[20][N];
int depth[N];
void dfs(int node, int par) {
//cout << "node = " << node << "\n";
DP[0][node] = par;
for(int i = 0; i < g[node].size(); i++) {
if(g[node][i].first != par) {
isDecreasing[0][g[node][i].first] = g[node][i].second;
isIncreasing[0][g[node][i].first] = g[node][i].second;
depth[g[node][i].first] = depth[node] + 1;
dfs(g[node][i].first, node);
}
}
}
int LCA(int x, int y) {
if(depth[x] < depth[y]) {
swap(x, y);
}
int diff = depth[x] - depth[y];
for(int i = 19; i >= 0; i--) {
if(diff >= (1 << i)) {
diff -= (1 << i);
x = DP[i][x];
}
}
if(x == y)
return x;
for(int i = 19; i >= 0; i--) {
if(DP[i][x] != DP[i][y]) {
x = DP[i][x];
y = DP[i][y];
}
}
return DP[0][x];
}
bool Satisfied(int a, int b, int cnt) {
int lca = LCA(a, b);
int diff = depth[b] - depth[lca];
int maxval = -1;
int lastvalhere = -1;
int prevval = -1;
for(int i = 19; i >= 0; i--) {
if(diff >= (1 << i)) {
diff -= (1 << i);
if(isIncreasing[i][b] == -1 || isIncreasing[0][b] <= prevval) {
return false;
}
maxval = max(maxval, isIncreasing[i][b]);
lastvalhere = max(lastvalhere, isIncreasing[i][b]);
prevval = isIncreasing[i][b];
b = DP[i][b];
}
}
diff = depth[a] - depth[b];
if(diff != 0) {
maxval = max(maxval, isDecreasing[0][a]);
}
//cout << "lastvalhere = " << lastvalhere << "\n";
prevval = INT_MAX;
for(int i = 19; i >= 0; i--) {
if(diff >= (1 << i)) {
diff -= (1 << i);
if(isDecreasing[i][a] == -1 || isDecreasing[0][a] >= prevval) {
return false;
}
if(diff == 0) {
if(lastvalhere >= isDecreasing[i][a]) {
return false;
}
}
prevval = isDecreasing[i][a];
a = DP[i][a];
}
}
//cout << "cnt = " << cnt << ", maxval = " << maxval << "\n";
if(maxval > cnt)
return false;
return true;
}
int dfs2(int node, int par, int curVal, int cur) {
int ans = 1;
for(int i = 0; i < g[node].size(); i++) {
if(g[node][i].first != par) {
if(g[node][i].second <= curVal || g[node][i].second > cur) {
continue;
}
else {
ans += dfs2(g[node][i].first, node, g[node][i].second, cur);
}
}
}
return ans;
}
void Solve() {
int n, q;
cin >> n >> q;
q += (n - 1);
vector<pair<char, pair<int, int> > > queries;
while(q--) {
char c;
cin >> c;
int a, b;
if(c == 'S') {
cin >> a >> b;
g[a].push_back({b, ++cnt});
g[b].push_back({a, cnt});
}
else if(c == 'Q') {
cin >> a >> b;
}
else {
cin >> a;
b = -1;
}
queries.push_back({c, {a, b}});
}
depth[1] = 0;
g[1].push_back({-1, 0});
isIncreasing[0][1] = -1;
isDecreasing[0][1] = -1;
dfs(1, -1);
for(int i = 1; i < 20; i++) {
for(int j = 1; j <= n; j++) {
if(DP[i - 1][j] == -1) {
DP[i][j] = -1;
}
else {
DP[i][j] = DP[i - 1][DP[i - 1][j]];
}
if(DP[i][j] == -1) {
isDecreasing[i][j] = -1;
isIncreasing[i][j] = -1;
}
else {
if(isDecreasing[i - 1][j] == -1 || isDecreasing[i - 1][DP[i - 1][j]] == -1) {
isDecreasing[i][j] = -1;
}
else if(isDecreasing[i - 1][j] <= isDecreasing[0][DP[i - 1][j]]) {
isDecreasing[i][j] = -1;
}
else {
isDecreasing[i][j] = isDecreasing[i - 1][DP[i - 1][j]];
}
if(isIncreasing[i - 1][j] == -1 || isIncreasing[i - 1][DP[i - 1][j]] == -1) {
isIncreasing[i][j] = -1;
}
else if(isIncreasing[i - 1][j] >= isIncreasing[0][DP[i - 1][j]]) {
isIncreasing[i][j] = -1;
}
else {
isIncreasing[i][j] = isIncreasing[i - 1][DP[i - 1][j]];
}
}
}
}
/*for(int i = 0; i < 20; i++) {
for(int j = 1; j <= n; j++) {
cout << isIncreasing[i][j] << " ";
}
cout << "\n";
}
for(int i = 0; i < 20; i++) {
for(int j = 1; j <= n; j++) {
cout << isDecreasing[i][j] << " ";
}
cout << "\n";
}*/
cnt = 0;
int val[n + 1];
for(int i = 0; i <= n; i++) {
val[i] = -1;
}
for(int i = 0; i < queries.size(); i++) {
char c = queries[i].first;
int a = queries[i].second.first, b = queries[i].second.second;
if(c == 'S') {
cnt++;
if(a == 1)
swap(a, b);
val[a] = cnt - 1;
}
else if(c == 'Q') {
if(Satisfied(a, b, cnt)) {
cout << "yes\n";
}
else {
cout << "no\n";
}
}
else {
if(a == 1) {
cout << cnt + 1 << "\n";
}
else {
if(val[a] == -1) {
cout << "1\n";
}
else {
cout << cnt - val[a] + 1 << "\n";
}
}
}
}
}
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
//cin >> t;
while(t--) {
Solve();
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
servers.cpp: In function 'void dfs(long long int, long long int)':
servers.cpp:14:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | for(int i = 0; i < g[node].size(); i++) {
| ~~^~~~~~~~~~~~~~~~
servers.cpp: In function 'long long int dfs2(long long int, long long int, long long int, long long int)':
servers.cpp:93:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(int i = 0; i < g[node].size(); i++) {
| ~~^~~~~~~~~~~~~~~~
servers.cpp: In function 'void Solve()':
servers.cpp:187:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<char, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
187 | for(int i = 0; i < queries.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... |
# | 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... |