oj.uz

답안 #1013534

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1013534 2024-07-03T15:34:22 Z PCTprobability Prize (CEOI22_prize) C++17
41 / 100
 3500 ms 600028 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<ll> node;
  ll n;
  segtree(){
  }
  segtree(ll _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];
    }
  }
  ll 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);
  }
  ll prod(ll l,ll r){
    return prod(l,r,0,n,1);
  }
};
struct HLD{
  vector<vector<ll>> g;
  vector<ll> p,nx,sz,in;
  ll now=0;
  segtree seg;
  HLD(vector<vector<ll>> _g,ll r){
    ll n=_g.size();
    g=_g;
    p.resize(n);
    nx.resize(n);
    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<ll>> g1,g2;
ll re;
vector<ll> 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;
  }
}
ll d1[1010101][2],d2[1010101][2];
vector<P> ask;
ll th[1010101];
ll now=0;
P dfs2(ll a,ll b){
  vector<P> 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};
}
ll ud1[1010101],ud2[1010101];
P dfs3(ll a,ll b){
  vector<P> d;
  vector<ll> es;
  for(auto e:g2[a]){
    if(e==b) continue;
    P 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<P> g3[1010101];
ll al=-1;
ll rt[1010101];
vector<ll> ok;
ll 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);
      ll 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();
  ll n,k,q,t;
  cin>>n>>k>>q>>t;
  ll r1,r2;
  vector<ll> 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<ll> 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<long long int, long long int> dfs2(ll, ll)':
Main.cpp:206:18: 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]
  206 |   for(int i=0;i+1<d.size();i++){
      |               ~~~^~~~~~~~~
Main.cpp: In function 'std::pair<long long int, long long int> dfs3(ll, ll)':
Main.cpp:229:18: 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]
  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<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  305 |   for(int i=0;i<ask.size();i++){
      |               ~^~~~~~~~~~~
Main.cpp:317:13: warning: 'r2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  317 |   dfs3(r2,-1);
      |             ^
Main.cpp:326:13: warning: 'r1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  326 |     if(th[i]&&i!=r1) ud1[i]=rt[i]-rt[p1[i]];
      |        ~~~~~^~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1779 ms 312952 KB Output is correct
2 Correct 1789 ms 313588 KB Output is correct
3 Correct 1764 ms 244724 KB Output is correct
4 Correct 1844 ms 244440 KB Output is correct
5 Correct 1769 ms 245204 KB Output is correct
6 Correct 1889 ms 255336 KB Output is correct
7 Correct 1716 ms 255368 KB Output is correct
8 Correct 1671 ms 255072 KB Output is correct
9 Correct 1529 ms 244672 KB Output is correct
10 Correct 1766 ms 245040 KB Output is correct
11 Correct 1579 ms 244156 KB Output is correct
12 Runtime error 1336 ms 244828 KB Execution killed with signal 13
13 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1896 ms 313524 KB Output is correct
2 Correct 1765 ms 312300 KB Output is correct
3 Correct 1884 ms 244572 KB Output is correct
4 Correct 2016 ms 245116 KB Output is correct
5 Correct 1776 ms 244756 KB Output is correct
6 Correct 1687 ms 254404 KB Output is correct
7 Runtime error 1367 ms 255772 KB Execution killed with signal 13
8 Halted 0 ms 0 KB -

Subtask #3
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1371 ms 297852 KB Output is correct
2 Correct 1380 ms 297804 KB Output is correct
3 Correct 1181 ms 230008 KB Output is correct
4 Correct 1113 ms 230016 KB Output is correct
5 Correct 1125 ms 229928 KB Output is correct
6 Correct 1258 ms 240516 KB Output is correct
7 Correct 1243 ms 240416 KB Output is correct
8 Correct 1226 ms 240444 KB Output is correct
9 Correct 1147 ms 242132 KB Output is correct
10 Correct 1119 ms 242064 KB Output is correct
11 Correct 1134 ms 242128 KB Output is correct
12 Correct 1242 ms 242044 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3348 ms 578152 KB Output is correct
2 Correct 3304 ms 578680 KB Output is correct
3 Correct 2763 ms 443016 KB Output is correct
4 Correct 2941 ms 443208 KB Output is correct
5 Correct 2648 ms 443084 KB Output is correct
6 Correct 2962 ms 464288 KB Output is correct
7 Correct 3140 ms 464416 KB Output is correct
8 Correct 3010 ms 464036 KB Output is correct
9 Correct 2928 ms 467360 KB Output is correct
10 Correct 3114 ms 467552 KB Output is correct
11 Correct 2975 ms 467088 KB Output is correct
12 Correct 2942 ms 467300 KB Output is correct

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3461 ms 600028 KB Output is correct
2 Correct 3492 ms 599852 KB Output is correct
3 Correct 3134 ms 462684 KB Output is correct
4 Correct 3257 ms 463952 KB Output is correct
5 Correct 3110 ms 462316 KB Output is correct
6 Correct 3417 ms 484708 KB Output is correct
7 Correct 3363 ms 483344 KB Output is correct
8 Correct 3375 ms 483908 KB Output is correct
9 Execution timed out 3509 ms 486932 KB Time limit exceeded
10 Halted 0 ms 0 KB -