Submission #1005349

#TimeUsernameProblemLanguageResultExecution timeMemory
1005349YassineBenYounesPrize (CEOI22_prize)C++17
0 / 100
290 ms85860 KiB
#include<bits/stdc++.h> typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef double db; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define pbds tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> using namespace __gnu_pbds; ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD) ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM) int dx[8] = {1, 0, 0, -1, 1, 1, -1, -1}; int dy[8] = {0, 1, -1, 0, 1, -1, -1, 1}; #define endl "\n" #define ss second #define ff first #define all(x) (x).begin() , (x).end() #define pb push_back #define vi vector<int> #define vii vector<pair<int,int>> #define vl vector<ll> #define vll vector<pair<ll,ll>> #define pii pair<int,int> #define pll pair<ll,ll> #define pdd pair<double,double> #define vdd vector<pdd> #define speed ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; ////////////////////Only Clear Code////////////////////////// void usaco_problem(){ freopen("milkvisits.in", "r", stdin); freopen("milkvisits.out", "w", stdout); } void init(){ #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif // ONLINE_JUDGE } //#define int ll const int mx = 5e5+5; const int LOG = 25; const int inf = 1e9; const ll mod = 998244353; vi tree1[mx]; vi tree2[mx]; int ind[mx]; int n, k, q, t; vi v; vii ask; int c = 0; void dfs(int node){ if(c == k)return; ind[node] = v.size(); v.pb(node); c++; for(int adj : tree1[node]){ if(c < k){ ask.pb({node, adj}); dfs(adj); } } } vector<vi> answers; ll pf[mx], pf1[mx]; ll dis[mx]; ll dislca[mx]; void run_case(){ cin >> n >> k >> q >> t; int root1 = -1, root2 = -1; for(int i = 1; i <= n;i++){ int a;cin >> a; if(a==-1)root1 = i; else tree1[a].pb(i); } for(int i = 1; i <= n;i++){ int a;cin >> a; if(a==-1)root2 = i; else tree2[a].pb(i); } dfs(root1); for(int x : v){ cout << x << " "; } cout << endl; cout.flush(); for(pii p : ask){ cout << "? " << p.ff << " " << p.ss << endl; } cout << "!" << endl; cout.flush(); for(pii p : ask){ ll a, b, c, d;cin >> a >> b >> c >> d; answers.pb({a, b}); dis[ind[p.ff]] = a+b; dislca[ind[p.ff]] = a; } pf[0] = dis[0]; for(int i = 1; i < v.size();i++){ pf[i] = pf[i-1] + dis[i]; } pf1[0] = dislca[0]; for(int i = 1; i < v.size();i++){ pf1[i] = pf1[i-1] + dislca[i]; } vl res; for(int i = 0; i < t;i++){ int a, b;cin >> a >> b;if(ind[b] < ind[a])swap(a, b); if(a==b)res.pb(0); else{ ll ans = pf[ind[b]-1] - (ind[a] == 0 ? 0 : pf[ind[a]-1]); ll ans1 = pf1[ind[b]-1] - pf1[ind[a]]; res.pb(ans-2*ans1); } } for(int i = 0;i < t;i++){ cout << res[i] << " " << res[i] << endl; } cout.flush(); } int main(){ speed; int t = 1; //cin >> t; while(t--){ run_case(); } } /* NEVER GIVE UP! DOING SMTHNG IS BETTER THAN DOING NTHNG!!! Your Guide when stuck: - Continue keyword only after reading the whole input - Don't use memset with testcases - Check for corner cases(n=1, n=0) - Check where you declare n(Be careful of declaring it globally and in main) */

Compilation message (stderr)

Main.cpp: In function 'void run_case()':
Main.cpp:102:21: warning: narrowing conversion of 'a' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
  102 |         answers.pb({a, b});
      |                     ^
Main.cpp:102:21: warning: narrowing conversion of 'a' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
Main.cpp:102:24: warning: narrowing conversion of 'b' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
  102 |         answers.pb({a, b});
      |                        ^
Main.cpp:102:24: warning: narrowing conversion of 'b' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
Main.cpp:107:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for(int i = 1; i < v.size();i++){
      |                    ~~^~~~~~~~~~
Main.cpp:111:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     for(int i = 1; i < v.size();i++){
      |                    ~~^~~~~~~~~~
Main.cpp:78:21: warning: variable 'root2' set but not used [-Wunused-but-set-variable]
   78 |     int root1 = -1, root2 = -1;
      |                     ^~~~~
Main.cpp: In function 'void usaco_problem()':
Main.cpp:33:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     freopen("milkvisits.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:34:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     freopen("milkvisits.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'void init()':
Main.cpp:40:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 | freopen("input.txt", "r", stdin);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:42:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 | freopen("output.txt", "w", stdout);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...