이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
const int N = 500010;
const int LOGN = 20;
vector <int> g[N];
int st;
int ans[N];
struct Binary_lifting{
int pai[N][LOGN], val[N][LOGN], h[N];
void dfs(int v, int p){
pai[v][0] = p;
val[v][0] = ans[v];
for(auto x : g[v]){
if(x == p) continue;
h[x] = h[v]+1;
dfs(x, v);
}
return;
}
void build(int n){
dfs(st, st);
for(int bit = 1;bit < LOGN;bit++){
for(int i = 1;i <= n;i++){
pai[i][bit] = pai[pai[i][bit-1]][bit-1];
val[i][bit] = val[i][bit-1] + val[pai[i][bit-1]][bit-1];
}
}
return;
}
int query(int a, int b){
if(h[a] > h[b]) swap(a, b);
int t = h[b]-h[a];
int res = 0;
for(int bit=0;bit < LOGN;bit++){
if((1<<bit)&t){
res += val[b][bit];
b = pai[b][bit];
}
}
if(a == b) return res;
for(int bit = LOGN-1;bit >= 0;bit--){
if(pai[a][bit] != pai[b][bit]){
res += val[a][bit];
res += val[b][bit];
a = pai[a][bit];
b = pai[b][bit];
}
}
return res+val[a][0]+val[b][0];
}
} bin;
int n, k,q , t;
int pai[N];
vector <int> vertices;
void dfs2(int v, int p){
if(v != p){
if(vertices.size() < k){
cout << "? " << v << ' ' << p << '\n';
}
}
if(vertices.size() < k) vertices.push_back(v);
for(auto x : g[v]){
if(x == p) continue;
dfs2(x, v);
}
return;
}
void dfs(int v, int p){
if(vertices.size()< k) vertices.push_back(v);
for(auto x : g[v]){
if(x == p) continue;
dfs(x, v);
}
return;
}
int main(){
cin >> n >> k >> q >> t;
for(int i = 1;i <= n;i++){
cin >> pai[i];
if(pai[i] == -1)st = i;
}
for(int i = 1;i <= n;i++){
cin >> pai[i];
if(pai[i] == -1) continue;
g[i].push_back(pai[i]);
g[pai[i]].push_back(i);
}
dfs(st, st);
for(auto x : vertices){
cout << x << ' ';
}
cout << '\n';
cout << flush;
vertices.clear();
dfs2(st, st);
cout << "!\n";
cout << flush;
for(auto v : vertices){
int cu;
if(pai[v] == -1) continue;
cin >> ans[v] >> cu >> cu >> cu;
}
bin.build(n);
vector <pair <int, int>> queries;
while(q--){
int a, b;
cin >> a >> b;
queries.push_back({a,b});
}
for(auto [a, b] : queries){
cout << bin.query(a,b) << ' ' << bin.query(a, b) << '\n';
}
cout << flush;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'void dfs2(int, int)':
Main.cpp:64:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
64 | if(vertices.size() < k){
| ~~~~~~~~~~~~~~~~^~~
Main.cpp:68:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
68 | if(vertices.size() < k) vertices.push_back(v);
| ~~~~~~~~~~~~~~~~^~~
Main.cpp: In function 'void dfs(int, int)':
Main.cpp:77:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
77 | if(vertices.size()< k) vertices.push_back(v);
| ~~~~~~~~~~~~~~~^~~
# | 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... |