| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 952647 |
2024-03-24T12:43:58 Z |
Vladth11 |
Prize (CEOI22_prize) |
C++14 |
|
1804 ms |
386400 KB |
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
const ll NMAX = 1000001;
const int INF = 1e9;
const ll nrbits = 20;
const ll MOD = 998244353;
const int VMAX = 10;
int n;
class Tree{
public:
vector <int> v[NMAX];
int dp[nrbits + 1][NMAX];
vector <int> preorder;
pii timp[NMAX];
int stamp, root;
void init(){
preorder.clear();
stamp = root = 0;
for(int i = 0; i <= n; i++){
v[i].clear();
timp[i].first = timp[i].second = 0;
}
for(int j = 0; j <= nrbits; j++){
for(int i = 0; i <= n; i++)
dp[j][i] = 0;
}
}
bool isParent(int a, int b){
return timp[a].first <= timp[b].first && timp[b].second <= timp[a].second;
}
int LCA(int a, int b){
int r = a, pas = nrbits;
while(pas >= 0){
int nxt = dp[pas][r];
if(nxt != 0 && !isParent(nxt, b)){
r = nxt;
}
pas--;
}
if(!isParent(r, b))
r = dp[0][r];
return r;
}
void setFather(int a, int b){
if(a == -1){
root = b;
return;
}
v[b].push_back(a);
v[a].push_back(b);
}
void DFS(int node, int p){
preorder.push_back(node);
timp[node].first = ++stamp;
dp[0][node] = p;
for(auto x : v[node]){
if(x == p) continue;
DFS(x, node);
}
timp[node].second = stamp;
}
void prec(){
for(int j = 1; j <= nrbits; j++){
for(int i = 1; i <= n; i++){
dp[j][i] = dp[j - 1][dp[j - 1][i]];
}
}
}
}arb1, arb2;
class DSU{ /// Momentan DSU doar cu numele
public:
vector <pii> v[NMAX];
int dist[NMAX];
void init(){
for(int i = 1; i <= n; i++){
v[i].clear();
dist[i] = 2e9;
}
}
void setDistance(int a, int b, int c){
v[a].push_back({b, c});
v[b].push_back({a, -c});
}
void DFS(int node){
for(auto x : v[node]){
if(dist[x.first] == 2e9){
dist[x.first] = x.second + dist[node];
DFS(x.first);
}
}
}
void baga(int x){
dist[x] = 0;
DFS(x);
}
}dsu1, dsu2;
pii sol[NMAX];
bool cmp(int a, int b){
return arb2.timp[a].first < arb2.timp[b].first;
}
signed main() {
#ifdef HOME
// ifstream cin(".in");
// ofstream cout(".out");
#endif // HOME
int k, q, t, rt1 = 0, rt2 = 0;
cin >> n >> k >> q >> t;
arb1.init();
arb2.init();
dsu1.init();
dsu2.init();
for(int i = 1; i <= n; i++){
int p;
cin >> p;
arb1.setFather(p, i);
}
for(int i = 1; i <= n; i++){
int p;
cin >> p;
arb2.setFather(p, i);
}
arb1.DFS(arb1.root, 0);
arb2.DFS(arb2.root, 0);
arb1.prec();
arb2.prec();
vector <int> chosen;
for(int i = 0; i < k; i++){
chosen.push_back(arb1.preorder[i]);
}
for(auto x : chosen){
cout << x << " ";
}
cout << "\n";
sort(chosen.begin(), chosen.end(), cmp);
for(int i = 0; i < chosen.size() - 1; i++){
cout << "? " << chosen[i] << " " << chosen[i + 1] << "\n";
}
cout << endl;
int minim = 2e9;
int cine = 0;
for(int i = 0; i < chosen.size() - 1; i++){
int a, b, c, d;
cin >> a >> b >> c >> d;
int lca1 = arb1.LCA(chosen[i], chosen[i + 1]);
int lca2 = arb2.LCA(chosen[i], chosen[i + 1]);
if(arb2.timp[lca2].first < minim){
minim = arb2.timp[lca2].first;
cine = lca2;
}
dsu1.setDistance(lca1, chosen[i], a);
dsu1.setDistance(lca1, chosen[i + 1], b);
dsu2.setDistance(lca2, chosen[i], c);
dsu2.setDistance(lca2, chosen[i + 1], d);
}
dsu1.baga(arb1.root);
dsu2.baga(cine);
for(int i = 0; i < t; i++){
int a, b;
cin >> a >> b;
int lca1 = arb1.LCA(a, b);
int lca2 = arb2.LCA(a, b);
sol[i] = {dsu1.dist[a] - 2 * dsu1.dist[lca1] + dsu1.dist[b], dsu2.dist[a] - 2 * dsu2.dist[lca2] + dsu2.dist[b]};
}
for(int i = 0; i < t; i++){
cout << sol[i].first << " " << sol[i].second << "\n";
}
cout << endl;
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:150:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
150 | for(int i = 0; i < chosen.size() - 1; i++){
| ~~^~~~~~~~~~~~~~~~~~~
Main.cpp:156:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
156 | for(int i = 0; i < chosen.size() - 1; i++){
| ~~^~~~~~~~~~~~~~~~~~~
Main.cpp:120:18: warning: unused variable 'rt1' [-Wunused-variable]
120 | int k, q, t, rt1 = 0, rt2 = 0;
| ^~~
Main.cpp:120:27: warning: unused variable 'rt2' [-Wunused-variable]
120 | int k, q, t, rt1 = 0, rt2 = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
875 ms |
257296 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
797 ms |
257584 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
841 ms |
257216 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1702 ms |
386152 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1804 ms |
386400 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
