oj.uz

답안 #1013578

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1013578 2024-07-03T16:41:03 Z PCTprobability Prize (CEOI22_prize) C++17
76 / 100
 3500 ms 511656 KB 
#include <bits/stdc++.h>
using namespace std;
/*#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif*/
using ll = long long;
using ld = long double;
using ull = unsigned long long;
#define endl "\n"
typedef pair<int, int> Pii;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REP3(i, m, n) for (int i = (m); (i) < int(n); ++ (i))
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define ALL(x) begin(x), end(x)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(s) (s).begin(),(s).end()
#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)
#define drep(i, n) drep2(i, n, 0)
#define rever(vec) reverse(vec.begin(), vec.end())
#define sor(vec) sort(vec.begin(), vec.end())
#define fi first
#define FOR_(n) for (ll _ = 0; (_) < (ll)(n); ++(_))
#define FOR(i, n) for (ll i = 0; (i) < (ll)(n); ++(i))
#define se second
#define pb push_back
#define P pair<ll,ll>
#define PQminll priority_queue<ll, vector<ll>, greater<ll>>
#define PQmaxll priority_queue<ll,vector<ll>,less<ll>>
#define PQminP priority_queue<P, vector<P>, greater<P>>
#define PQmaxP priority_queue<P,vector<P>,less<P>>
#define NP next_permutation
#define die(a) {cout<<a<<endl;return 0;}
#define dier(a) {return a;}
//const ll mod = 1000000009;
const ll mod = 998244353;
//const ll mod = 1000000007;
const ll inf = 4100000000000000000ll;
const ld eps = ld(0.00000000001);
static const long double pi = 3.141592653589793;
template<class T>void vcin(vector<T> &n){for(int i=0;i<int(n.size());i++) cin>>n[i];}
template<class T,class K>void vcin(vector<T> &n,vector<K> &m){for(int i=0;i<int(n.size());i++) cin>>n[i]>>m[i];}
template<class T>void vcout(vector<T> &n){for(int i=0;i<int(n.size());i++){cout<<n[i]<<" ";}cout<<endl;}
template<class T>void vcin(vector<vector<T>> &n){for(int i=0;i<int(n.size());i++){for(int j=0;j<int(n[i].size());j++){cin>>n[i][j];}}}
template<class T>void vcout(vector<vector<T>> &n){for(int i=0;i<int(n.size());i++){for(int j=0;j<int(n[i].size());j++){cout<<n[i][j]<<" ";}cout<<endl;}cout<<endl;}
void yes(bool a){cout<<(a?"yes":"no")<<endl;}
void YES(bool a){cout<<(a?"YES":"NO")<<endl;}
void Yes(bool a){cout<<(a?"Yes":"No")<<endl;}
void possible(bool a){ cout<<(a?"possible":"impossible")<<endl; }
void Possible(bool a){ cout<<(a?"Possible":"Impossible")<<endl; }
void POSSIBLE(bool a){ cout<<(a?"POSSIBLE":"IMPOSSIBLE")<<endl; }
#define FOR_R(i, n) for (ll i = (ll)(n)-1; (i) >= 0; --(i))
template<class T>auto min(const T& a){ return *min_element(all(a)); }
template<class T>auto max(const T& a){ return *max_element(all(a)); }
template<class T,class F>void print(pair<T,F> a){cout<<a.fi<<" "<<a.se<<endl;}
template<class T>bool chmax(T &a,const T b) { if (a<b) { a=b; return 1; } return 0;}
template<class T>bool chmin(T &a,const T b) { if (b<a) { a=b; return 1; } return 0;}
template<class T> void ifmin(T t,T u){if(t>u){cout<<-1<<endl;}else{cout<<t<<endl;}}
template<class T> void ifmax(T t,T u){if(t>u){cout<<-1<<endl;}else{cout<<t<<endl;}}
ll fastgcd(ll u,ll v){ll shl=0;while(u&&v&&u!=v){bool eu=!(u&1);bool ev=!(v&1);if(eu&&ev){++shl;u>>=1;v>>=1;}else if(eu&&!ev){u>>=1;}else if(!eu&&ev){v>>=1;}else if(u>=v){u=(u-v)>>1;}else{ll tmp=u;u=(v-u)>>1;v=tmp;}}return !u?v<<shl:u<<shl;}
ll modPow(ll a, ll n, ll mod) { if(mod==1) return 0;ll ret = 1; ll p = a % mod; while (n) { if (n & 1) ret = ret * p % mod; p = p * p % mod; n >>= 1; } return ret; }
vector<ll> divisor(ll x){ vector<ll> ans; for(ll i = 1; i * i <= x; i++){ if(x % i == 0) {ans.push_back(i); if(i*i!=x){ ans.push_back(x / ans[i]);}}}sor(ans); return ans; }
ll pop(ll x){return __builtin_popcountll(x);}
ll poplong(ll x){ll y=-1;while(x){x/=2;y++;}return y;}
P hyou(P a){ll x=fastgcd(abs(a.fi),abs(a.se));a.fi/=x;a.se/=x;if(a.se<0){a.fi*=-1;a.se*=-1;}return a;}
P Pplus(P a,P b){ return hyou({a.fi*b.se+b.fi*a.se,a.se*b.se});}
P Ptimes(P a,ll b){ return hyou({a.fi*b,a.se});}
P Ptimes(P a,P b){ return hyou({a.fi*b.fi,a.se*b.se});}
P Pminus(P a,P b){ return hyou({a.fi*b.se-b.fi*a.se,a.se*b.se});}
P Pgyaku(P a){ return hyou({a.se,a.fi});}
 
void cincout(){
  ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
  cout<< fixed << setprecision(15);
}
struct segtree{
  vector<int> node;
  int n;
  segtree(){
  }
  segtree(int _n){
    n=1;
    while(n<_n) n*=2;
    node.resize(2*n);
  }
  void set(ll i,ll v){
    i+=n;
    node[i]=v;
    while(i){
      i/=2;
      node[i]=node[2*i]+node[2*i+1];
    }
  }
  int prod(ll l,ll r,ll a,ll b,ll k){
    if(r<=a||b<=l) return 0;
    if(l<=a&&b<=r) return node[k];
    return prod(l,r,a,(a+b)/2,2*k)+prod(l,r,(a+b)/2,b,2*k+1);
  }
  int prod(ll l,ll r){
    return prod(l,r,0,n,1);
  }
};
struct HLD{
  vector<vector<int>> g;
  vector<int> p,nx,sz,in;
  ll now=0;
  segtree seg;
  HLD(vector<vector<int>> _g,ll r){
    ll n=_g.size();
    g=_g;
    p.resize(n);
    nx.resize(n,r);
    sz.resize(n);
    in.resize(n);
    dfs_sz(r,-1);
    now=0;
    dfs_hld(r,-1);
    seg=segtree(n);
  }
  void dfs_sz(int a,int b){
    if(g[a].size()&&g[a][0]==b){
      swap(g[a][0],g[a].back());
    }
    for(auto &e:g[a]){
      if(e==b) continue;
      dfs_sz(e,a);
      p[e]=a;
      sz[a]+=sz[e];
      if(sz[e]>sz[g[a][0]]){
        swap(e,g[a][0]);
      }
    }
    sz[a]++;
  }
  void dfs_hld(int a,int b){
    in[a]=now;
    now++;
    for(auto &e:g[a]){
      if(e==b) continue;
      if(e==g[a][0]){
        nx[e]=nx[a];
      }
      else{
        nx[e]=e;
      }
      dfs_hld(e,a);
    }
  }
  ll lca(ll u,ll v){
    while(true){
      if(in[u]>in[v]) swap(u,v);
      if(nx[u]==nx[v]) return u;
      v=p[nx[v]];
    }
  }
  void set(ll i,ll x){
    seg.set(in[i],x);
  }
  ll prod(ll u,ll v){
    ll l=lca(u,v);
    ll ans=0;
    while(nx[u]!=nx[l]){
      ans+=seg.prod(in[nx[u]],in[u]+1);
      u=p[nx[u]];
    }
    while(nx[v]!=nx[l]){
      ans+=seg.prod(in[nx[v]],in[v]+1);
      v=p[nx[v]];
    }
    ans+=seg.prod(in[l],in[u]+1);
    ans+=seg.prod(in[l]+1,in[v]+1);
    return ans;
  }
};
vector<vector<int>> g1,g2;
int re;
vector<int> v;
void dfs(ll a,ll b){
  if(re==0) return;
  v.pb(a);
  re--;
  if(re==0) return;
  for(auto e:g1[a]){
    if(e==b) continue;
    dfs(e,a);
    if(re==0) return;
  }
}
int d1[1010101][2],d2[1010101][2];
vector<pair<int,int>> ask;
int th[1010101];
int now=0;
pair<int,int> dfs2(ll a,ll b){
  vector<pair<int,int>> d;
  for(auto e:g2[a]){
    if(e==b) continue;
    P v=dfs2(e,a);
    if(v.fi==-1) continue;
    d.pb(v);
  }
  if(th[a]&&d.size()){
    ask.pb({a,d[0].fi});
  }
  for(int i=0;i+1<d.size();i++){
    ask.pb({d[i].fi,d[i+1].fi});
  }
  if(th[a]) return {a,0};
  else if(d.size()) return d[0];
  else return {-1,-1};
}
int ud1[1010101],ud2[1010101];
pair<int,int> dfs3(ll a,ll b){
  vector<pair<int,int>> d;
  vector<int> es;
  for(auto e:g2[a]){
    if(e==b) continue;
    pair<int,int> v=dfs3(e,a);
    if(v.fi==-1) continue;
    d.pb(v);
    es.pb(e);
  }
  if(th[a]&&d.size()){
    //ask.pb({a,d[0].fi});
    ud2[es[0]]=d2[now][1]-d[0].se;
    now++;
  }
  for(int i=0;i+1<d.size();i++){
   // ask.pb({d[i].fi,d[i+1].fi});
    ud2[es[i]]=d2[now][0]-d[i].se;
    ud2[es[i+1]]=d2[now][1]-d[i+1].se;
    now++;
  }
  if(th[a]) return {a,0};
  else if(d.size()) return {d[0].fi,d[0].se+ud2[es[0]]};
  else return {-1,-1};
}
vector<pair<int,int>> g3[1010101];
int al=-1;
int rt[1010101];
vector<ll> ok;
int ho=0;
void dfs4(ll a,ll b,HLD &hld){
  if(al==-1){
    ok.pb(a);
    al=a;
  }
  for(auto e:g3[a]){
    ll c=e.fi,i=e.se;
    if(c==b) continue;
    if(hld.lca(al,hld.lca(c,a))==al){
      if(ask[i].fi==c) rt[c]=rt[a]+d1[i][0]-d1[i][1];
      else rt[c]=rt[a]-d1[i][0]+d1[i][1];
    }
    else{
      al=hld.lca(c,a);
      int pl=-(rt[a]+ho);
      if(ask[i].fi==a) pl+=d1[i][0];
      else pl+=d1[i][1];
      ho+=pl;
      if(ask[i].fi==c) rt[c]=d1[i][0]-ho;
      else rt[c]=d1[i][1]-ho;
    }
    ok.pb(c);
    dfs4(c,a,hld);
  }
}
int main(){
  //cincout();
  int n,k,q,t;
  cin>>n>>k>>q>>t;
  int r1,r2;
  vector<int> p1(n),p2(n);
  vcin(p1);
  vcin(p2);
  g1.resize(n);
  g2.resize(n);
  for(auto &e:p1){
    if(e!=-1) e--;
  }
  for(auto &e:p2){
    if(e!=-1) e--;
  }
  for(int i=0;i<n;i++){
    if(p1[i]==-1) r1=i;
    else{
      g1[p1[i]].pb(i);
      g1[i].pb(p1[i]);
    }
    if(p2[i]==-1) r2=i;
    else{
      g2[p2[i]].pb(i);
      g2[i].pb(p2[i]);
    }
  }
  HLD hld1(g1,r1),hld2(g2,r2);
  re=k;
  dfs(r1,-1);
  for(auto e:v) cout<<e+1<<" ";
  cout<<endl;
  cout.flush();
  for(auto e:v) th[e]++;
  dfs2(r2,-1);
  for(int i=0;i<ask.size();i++){
    g3[ask[i].fi].pb({ask[i].se,i});
    g3[ask[i].se].pb({ask[i].fi,i});
    cout<<"?"<<" "<<ask[i].fi+1<<" "<<ask[i].se+1<<endl;
    cout.flush();
  }
  cout<<"!"<<endl;
  cout.flush();
  vector<int> a(t),b(t);
  for(int i=0;i<k-1;i++) cin>>d1[i][0]>>d1[i][1]>>d2[i][0]>>d2[i][1];
  for(int i=0;i<t;i++) cin>>a[i]>>b[i];
  now=0;
  dfs3(r2,-1);
  for(int i=0;i<n;i++){
    if(g3[i].size()){
      dfs4(i,-1,hld1);
      break;
    }
  }
  for(auto e:ok) rt[e]+=ho;
  for(int i=0;i<n;i++){
    if(th[i]&&i!=r1) ud1[i]=rt[i]-rt[p1[i]];
  }
  /*
  for(int i=0;i<n;i++) cout<<ud1[i]<<" ";
  cout<<endl;
  for(int i=0;i<n;i++) cout<<rt[i]<<" ";
  cout<<endl;
  for(int i=0;i<n;i++) cout<<ud2[i]<<" ";
  cout<<endl;
  */
  for(int i=0;i<n;i++){
    hld1.set(i,ud1[i]);
    hld2.set(i,ud2[i]);
  }
  for(int i=0;i<t;i++){
    a[i]--;
    b[i]--;
    cout<<hld1.prod(a[i],b[i])-ud1[hld1.lca(a[i],b[i])]<<" "<<hld2.prod(a[i],b[i])-ud2[hld2.lca(a[i],b[i])]<<endl;
    cout.flush();
  }
  return 0;
}

Compilation message

Main.cpp: In function 'std::pair<int, int> dfs2(ll, ll)':
Main.cpp:206:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  206 |   for(int i=0;i+1<d.size();i++){
      |               ~~~^~~~~~~~~
Main.cpp: In function 'std::pair<int, int> dfs3(ll, ll)':
Main.cpp:229:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  229 |   for(int i=0;i+1<d.size();i++){
      |               ~~~^~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:305:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  305 |   for(int i=0;i<ask.size();i++){
      |               ~^~~~~~~~~~~
Main.cpp:297:29: warning: 'r2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  297 |   HLD hld1(g1,r1),hld2(g2,r2);
      |                             ^
Main.cpp:297:17: warning: 'r1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  297 |   HLD hld1(g1,r1),hld2(g2,r2);
      |                 ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1410 ms 268312 KB Output is correct
2 Correct 1440 ms 268740 KB Output is correct
3 Correct 1399 ms 199356 KB Output is correct
4 Correct 1618 ms 199192 KB Output is correct
5 Correct 1445 ms 199684 KB Output is correct
6 Correct 1407 ms 211060 KB Output is correct
7 Correct 1442 ms 211464 KB Output is correct
8 Correct 1486 ms 210836 KB Output is correct
9 Correct 1405 ms 199348 KB Output is correct
10 Correct 1704 ms 199612 KB Output is correct
11 Correct 1641 ms 199160 KB Output is correct
12 Correct 1584 ms 199476 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1528 ms 268688 KB Output is correct
2 Correct 1573 ms 268048 KB Output is correct
3 Correct 1467 ms 199304 KB Output is correct
4 Correct 1522 ms 199732 KB Output is correct
5 Correct 1527 ms 199428 KB Output is correct
6 Correct 1390 ms 210656 KB Output is correct
7 Correct 1431 ms 211308 KB Output is correct
8 Correct 1569 ms 211152 KB Output is correct
9 Correct 1531 ms 211640 KB Output is correct
10 Correct 1505 ms 211924 KB Output is correct
11 Correct 1505 ms 211412 KB Output is correct
12 Correct 1705 ms 211872 KB Output is correct

Subtask #3
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1272 ms 262016 KB Output is correct
2 Correct 1298 ms 262016 KB Output is correct
3 Correct 1016 ms 193408 KB Output is correct
4 Correct 1008 ms 193488 KB Output is correct
5 Correct 1133 ms 193384 KB Output is correct
6 Correct 1202 ms 204924 KB Output is correct
7 Correct 1197 ms 204748 KB Output is correct
8 Correct 1155 ms 204924 KB Output is correct
9 Correct 1059 ms 205676 KB Output is correct
10 Correct 1068 ms 205584 KB Output is correct
11 Correct 1002 ms 205440 KB Output is correct
12 Correct 1131 ms 205436 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3267 ms 504480 KB Output is correct
2 Correct 3230 ms 504908 KB Output is correct
3 Correct 2515 ms 367532 KB Output is correct
4 Correct 2665 ms 367424 KB Output is correct
5 Correct 2604 ms 367424 KB Output is correct
6 Correct 2843 ms 390544 KB Output is correct
7 Correct 2777 ms 390740 KB Output is correct
8 Correct 2957 ms 390504 KB Output is correct
9 Correct 3183 ms 391704 KB Output is correct
10 Correct 2944 ms 391728 KB Output is correct
11 Correct 3115 ms 391492 KB Output is correct
12 Correct 3222 ms 391704 KB Output is correct

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3573 ms 511656 KB Time limit exceeded
2 Halted 0 ms 0 KB -