oj.uz

답안 #1013575

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1013575 2024-07-03T16:36:55 Z PCTprobability Prize (CEOI22_prize) C++17
76 / 100
 3500 ms 600068 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,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<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
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1490 ms 312736 KB Output is correct
2 Correct 1480 ms 313440 KB Output is correct
3 Correct 1450 ms 244576 KB Output is correct
4 Correct 1450 ms 244552 KB Output is correct
5 Correct 1576 ms 245200 KB Output is correct
6 Correct 1548 ms 255564 KB Output is correct
7 Correct 1678 ms 255252 KB Output is correct
8 Correct 1597 ms 255148 KB Output is correct
9 Correct 1491 ms 244388 KB Output is correct
10 Correct 1558 ms 245056 KB Output is correct
11 Correct 1641 ms 244164 KB Output is correct
12 Correct 1805 ms 244896 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1692 ms 313516 KB Output is correct
2 Correct 1579 ms 312500 KB Output is correct
3 Correct 1670 ms 244552 KB Output is correct
4 Correct 1593 ms 245292 KB Output is correct
5 Correct 1719 ms 244764 KB Output is correct
6 Correct 1680 ms 254744 KB Output is correct
7 Correct 1773 ms 255368 KB Output is correct
8 Correct 1738 ms 255676 KB Output is correct
9 Correct 1737 ms 257168 KB Output is correct
10 Correct 1755 ms 257432 KB Output is correct
11 Correct 1674 ms 256384 KB Output is correct
12 Correct 1719 ms 257536 KB Output is correct

Subtask #3
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1324 ms 297968 KB Output is correct
2 Correct 1378 ms 297956 KB Output is correct
3 Correct 1100 ms 230108 KB Output is correct
4 Correct 1097 ms 230064 KB Output is correct
5 Correct 1068 ms 229916 KB Output is correct
6 Correct 1234 ms 240668 KB Output is correct
7 Correct 1178 ms 240416 KB Output is correct
8 Correct 1189 ms 240420 KB Output is correct
9 Correct 1153 ms 242048 KB Output is correct
10 Correct 1207 ms 242080 KB Output is correct
11 Correct 1171 ms 242044 KB Output is correct
12 Correct 1157 ms 242048 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3372 ms 578280 KB Output is correct
2 Correct 3288 ms 578452 KB Output is correct
3 Correct 2772 ms 443092 KB Output is correct
4 Correct 2788 ms 443312 KB Output is correct
5 Correct 2673 ms 443260 KB Output is correct
6 Correct 2948 ms 464088 KB Output is correct
7 Correct 2993 ms 464336 KB Output is correct
8 Correct 3249 ms 463972 KB Output is correct
9 Correct 2843 ms 467492 KB Output is correct
10 Correct 2956 ms 467636 KB Output is correct
11 Correct 2945 ms 467092 KB Output is correct
12 Correct 2844 ms 467360 KB Output is correct

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3451 ms 600068 KB Output is correct
2 Execution timed out 3527 ms 599736 KB Time limit exceeded
3 Halted 0 ms 0 KB -