| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1004649 |
2024-06-21T11:18:29 Z |
ErJ |
Prize (CEOI22_prize) |
C++17 |
|
3500 ms |
174744 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<ll>
#define pp pair<ll, ll>
#define vp vector<pp>
#define vvi vector<vi>
#define inf 1000000000
#define rep(i,n) for(int i = 0; i < n; i++)
vvi edges, edges2, edges3;
int k;
void dfs(int u, int par, int last){
if(u < k && (u != last)) {
edges3[u].push_back(last);
edges3[last].push_back(u);
last = u;
}
for(int v : edges[u]){
if(par != v){
dfs(v, u, last);
}
}
}
vector<pp> Itree;
void init(int n){
while(n & (n-1)) n++;
Itree.resize(2*n, {inf, inf});
}
void update(int ind, pp val){
ind += Itree.size() / 2;
Itree[ind] = val;
while(ind > 1){
ind /= 2;
Itree[ind] = min(Itree[2*ind], Itree[2*ind + 1]);
}
}
pp get2(ll u, ll l , ll r, ll a, ll b){
if(l == a && r == b) {
return Itree[u];
}
ll s = (a + b) / 2;
if(r <= s){
return get2(2*u, l, r, a, s);
}else if(l >= s){
return get2(2*u + 1, l, r, s, b);
}else{
return min(get2(2*u, l, s, a, s), get2(2*u + 1, s, r, s, b));
}
}
pp get(ll l, ll r){
return get2(1, l, r, 0, Itree.size() / 2);
}
vector<pp> eulerTour;
vi inEuler;
void euler(int u, int par, int hlad){
inEuler[u] = eulerTour.size();
for(int v : edges3[u]){
if(v != par){
eulerTour.push_back({hlad, u});
euler(v, u, hlad + 1);
}
}
eulerTour.push_back({hlad, u});
}
ll lca(ll u, ll v){
return get(min(inEuler[u], inEuler[v]), max(inEuler[u], inEuler[v]) + 1).second;
}
vi dist;
vvi val;
void dfsDist(int u, int par){
rep(i, edges3[u].size()){
int v = edges3[u][i];
if(v != par){
dist[v] = dist[u] + val[u][i];
dfsDist(v, u);
}
}
}
ll query(ll u, ll v){
ll LCA = lca(u, v);
ll ans = dist[u] + dist[v] - 2*dist[LCA];
return ans;
}
int main(){
int n, q, t;
cin >> n >> k >> q >> t;
edges.resize(n);
int root = -1;
rep(i, n){
int u;
cin >> u;
if(u == -1){
root = i;
}else{
u--;
edges[u].push_back(i);
edges[i].push_back(u);
}
}
int root2 = -1;
edges2.resize(n);
rep(i, n){
int u;
cin >> u;
if(u == -1){
root2 = i;
}else{
u--;
edges2[u].push_back(i);
edges2[i].push_back(u);
}
}
edges3.resize(k);
dfs(0, -1, 0);
vp quest;
val.resize(k);
rep(i, edges3.size()){
val[i].resize(edges3[i].size());
rep(j, edges3[i].size()){
int u = edges3[i][j];
if(i < u){
quest.push_back({i, j});
cout << "? " << i + 1 << " " << u + 1 << endl;
}
}
}
cout << "!" << endl;
cout.flush();
inEuler.resize(k);
euler(0, -1, 0);
init(eulerTour.size());
rep(i, eulerTour.size()){
update(i, eulerTour[i]);
}
rep(i, k - 1){
int a, b, c, d;
cin >> a >> b >> c >> d;
val[quest[i].first][quest[i].second] = a + b;
}
dist.resize(k, 0);
dfsDist(0, -1);
rep(i, t){
int u, v;
cin >> u >> v;
u--; v--;
ll ans = query(u, v);
cout << ans << " "<< ans << endl;
}
}
Compilation message
Main.cpp: In function 'void dfsDist(int, int)':
Main.cpp:11:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | #define rep(i,n) for(int i = 0; i < n; i++)
......
86 | rep(i, edges3[u].size()){
| ~~~~~~~~~~~~~~~~~~~
Main.cpp:86:5: note: in expansion of macro 'rep'
86 | rep(i, edges3[u].size()){
| ^~~
Main.cpp: In function 'int main()':
Main.cpp:11:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | #define rep(i,n) for(int i = 0; i < n; i++)
......
134 | rep(i, edges3.size()){
| ~~~~~~~~~~~~~~~~
Main.cpp:134:5: note: in expansion of macro 'rep'
134 | rep(i, edges3.size()){
| ^~~
Main.cpp:11:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | #define rep(i,n) for(int i = 0; i < n; i++)
......
136 | rep(j, edges3[i].size()){
| ~~~~~~~~~~~~~~~~~~~
Main.cpp:136:9: note: in expansion of macro 'rep'
136 | rep(j, edges3[i].size()){
| ^~~
Main.cpp:11:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | #define rep(i,n) for(int i = 0; i < n; i++)
......
149 | rep(i, eulerTour.size()){
| ~~~~~~~~~~~~~~~~~~~
Main.cpp:149:5: note: in expansion of macro 'rep'
149 | rep(i, eulerTour.size()){
| ^~~
Main.cpp:105:9: warning: variable 'root' set but not used [-Wunused-but-set-variable]
105 | int root = -1;
| ^~~~
Main.cpp:117:9: warning: variable 'root2' set but not used [-Wunused-but-set-variable]
117 | int root2 = -1;
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
399 ms |
89428 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
426 ms |
83352 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3529 ms |
87952 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3530 ms |
163268 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1054 ms |
174744 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
