QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#853204#9732. Gathering Mushroomsucup-team112#WA 69ms3988kbC++2315.3kb2025-01-11 16:08:532025-01-11 16:08:58

Judging History

你现在查看的是最新测评结果

  • [2025-01-11 16:08:58]
  • 评测
  • 测评结果：WA
  • 用时：69ms
  • 内存：3988kb
查看
  • [2025-01-11 16:08:53]
  • 提交

answer


//#define _GLIBCXX_DEBUG

//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>
using namespace std;


#ifdef LOCAL
#include <debug_print.hpp>
#define OUT(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)
#else
#define OUT(...) (static_cast<void>(0))
#endif

#define endl '\n'
#define lfs cout<<fixed<<setprecision(15)
#define ALL(a)  (a).begin(),(a).end()
#define ALLR(a)  (a).rbegin(),(a).rend()
#define UNIQUE(a) (a).erase(unique((a).begin(),(a).end()),(a).end())
#define spa << " " <<
#define fi first
#define se second
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define EB emplace_back
#define rep(i,n,m) for(ll i = (n); i < (ll)(m); i++)
#define rrep(i,n,m) for(ll i = (ll)(m) - 1; i >= (ll)(n); i--)

namespace template_tute{
  using ll = long long;
  using ld = long double;
  const ll MOD1 = 1e9+7;
  const ll MOD9 = 998244353;
  const ll INF = 4.1e18;
  using P = pair<ll, ll>;
  template<typename T> using PQ = priority_queue<T>;
  template<typename T> using QP = priority_queue<T,vector<T>,greater<T>>;
  template<typename T1, typename T2>bool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;}
  template<typename T1, typename T2>bool chmax(T1 &a,T2 b){if(a<b){a=b;return true;}else return false;}
  ll median(ll a,ll b, ll c){return a+b+c-max<ll>({a,b,c})-min<ll>({a,b,c});}
  void ans1(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
  void ans2(bool x){if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
  void ans3(bool x){if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
  template<typename T1,typename T2>void ans(bool x,T1 y,T2 z){if(x)cout<<y<<endl;else cout<<z<<endl;}  
  template<typename T1,typename T2,typename T3>void anss(T1 x,T2 y,T3 z){ans(x!=y,x,z);};  
  template<typename T>void debug(const T &v,ll h,ll w,string sv=" "){for(ll i=0;i<h;i++){cout<<v[i][0];for(ll j=1;j<w;j++)cout<<sv<<v[i][j];cout<<endl;}};
  template<typename T>void debug(const T &v,ll n,string sv=" "){if(n!=0)cout<<v[0];for(ll i=1;i<n;i++)cout<<sv<<v[i];cout<<endl;};
  template<typename T>void debug(const vector<T>&v){debug(v,v.size());}
  template<typename T>void debug(const vector<vector<T>>&v){for(auto &vv:v)debug(vv,vv.size());}
  template<typename T>void debug(stack<T> st){while(!st.empty()){cout<<st.top()<<" ";st.pop();}cout<<endl;}
  template<typename T>void debug(queue<T> st){while(!st.empty()){cout<<st.front()<<" ";st.pop();}cout<<endl;}
  template<typename T>void debug(deque<T> st){while(!st.empty()){cout<<st.front()<<" ";st.pop_front();}cout<<endl;}
  template<typename T>void debug(PQ<T> st){while(!st.empty()){cout<<st.top()<<" ";st.pop();}cout<<endl;}
  template<typename T>void debug(QP<T> st){while(!st.empty()){cout<<st.top()<<" ";st.pop();}cout<<endl;}
  template<typename T>void debug(const set<T>&v){for(auto z:v)cout<<z<<" ";cout<<endl;}
  template<typename T>void debug(const multiset<T>&v){for(auto z:v)cout<<z<<" ";cout<<endl;}
  template<typename T,size_t size>void debug(const array<T, size> &a){for(auto z:a)cout<<z<<" ";cout<<endl;}
  template<typename T,typename V>void debug(const map<T,V>&v){for(auto z:v)cout<<"["<<z.first<<"]="<<z.second<<",";cout<<endl;}
  template<typename T>vector<vector<T>>vec(ll x, ll y, T w){vector<vector<T>>v(x,vector<T>(y,w));return v;}
  vector<ll>dx={1,-1,0,0,1,1,-1,-1};vector<ll>dy={0,0,1,-1,1,-1,1,-1};
  template<typename T>vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
  template<typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v(ts...))>(a,make_v(ts...));}
  template<typename T1, typename T2>ostream &operator<<(ostream &os, const pair<T1, T2>&p){return os << "(" << p.first << "," << p.second << ")";}
  template<typename T>ostream &operator<<(ostream &os, const vector<T> &v){os<<"[";for(auto &z:v)os << z << ",";os<<"]"; return os;}
  template<typename T>void rearrange(vector<int>&ord, vector<T>&v){
    auto tmp = v;
    for(int i=0;i<tmp.size();i++)v[i] = tmp[ord[i]];
  }
  template<typename Head, typename... Tail>void rearrange(vector<int>&ord,Head&& head, Tail&&... tail){
    rearrange(ord, head);
    rearrange(ord, tail...);
  }
  template<typename T> vector<int> ascend(const vector<T>&v){
    vector<int>ord(v.size());iota(ord.begin(),ord.end(),0);
    sort(ord.begin(),ord.end(),[&](int i,int j){return make_pair(v[i],i)<make_pair(v[j],j);});
    return ord;
  }
  template<typename T> vector<int> descend(const vector<T>&v){
    vector<int>ord(v.size());iota(ord.begin(),ord.end(),0);
    sort(ord.begin(),ord.end(),[&](int i,int j){return make_pair(v[i],-i)>make_pair(v[j],-j);});
    return ord;
  }
  template<typename T> vector<T> inv_perm(const vector<T>&ord){
    vector<T>inv(ord.size());
    for(int i=0;i<ord.size();i++)inv[ord[i]] = i;
    return inv;
  }
  ll FLOOR(ll n,ll div){assert(div>0);return n>=0?n/div:(n-div+1)/div;}
  ll CEIL(ll n,ll div){assert(div>0);return n>=0?(n+div-1)/div:n/div;}
  ll digitsum(ll n){ll ret=0;while(n){ret+=n%10;n/=10;}return ret;}
  ll modulo(ll n,ll d){return (n%d+d)%d;};
  template<typename T>T min(const vector<T>&v){return *min_element(v.begin(),v.end());}
  template<typename T>T max(const vector<T>&v){return *max_element(v.begin(),v.end());}
  template<typename T>T acc(const vector<T>&v){return accumulate(v.begin(),v.end(),T(0));};
  template<typename T>T reverse(const T &v){return T(v.rbegin(),v.rend());};
  //mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
  int popcount(ll x){return __builtin_popcountll(x);};
  int poplow(ll x){return __builtin_ctzll(x);};
  int pophigh(ll x){return 63 - __builtin_clzll(x);};
  template<typename T>T poll(queue<T> &q){auto ret=q.front();q.pop();return ret;};
  template<typename T>T poll(priority_queue<T> &q){auto ret=q.top();q.pop();return ret;};
  template<typename T>T poll(QP<T> &q){auto ret=q.top();q.pop();return ret;};
  template<typename T>T poll(stack<T> &s){auto ret=s.top();s.pop();return ret;};
  ll MULT(ll x,ll y){if(LLONG_MAX/x<=y)return LLONG_MAX;return x*y;}
  ll POW2(ll x, ll k){ll ret=1,mul=x;while(k){if(mul==LLONG_MAX)return LLONG_MAX;if(k&1)ret=MULT(ret,mul);mul=MULT(mul,mul);k>>=1;}return ret;}
  ll POW(ll x, ll k){ll ret=1;for(int i=0;i<k;i++){if(LLONG_MAX/x<=ret)return LLONG_MAX;ret*=x;}return ret;}
  std::ostream &operator<<(std::ostream &dest, __int128_t value) {
    std::ostream::sentry s(dest);
    if (s) {
      __uint128_t tmp = value < 0 ? -value : value;
      char buffer[128];
      char *d = std::end(buffer);
      do {
        --d;
        *d = "0123456789"[tmp % 10];
        tmp /= 10;
      } while (tmp != 0);
      if (value < 0) {
        --d;
        *d = '-';
      }
      int len = std::end(buffer) - d;
      if (dest.rdbuf()->sputn(d, len) != len) {
        dest.setstate(std::ios_base::badbit);
      }
    }
    return dest;
  }
  namespace converter{
    int dict[500];
    const string lower="abcdefghijklmnopqrstuvwxyz";
    const string upper="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    const string digit="0123456789";
    const string digit1="123456789";
    void regi_str(const string &t){
      for(int i=0;i<t.size();i++){
        dict[t[i]]=i;
      }
    }
    void regi_int(const string &t){
      for(int i=0;i<t.size();i++){
        dict[i]=t[i];
      }
    }
    vector<int>to_int(const string &s,const string &t){
      regi_str(t);
      vector<int>ret(s.size());
      for(int i=0;i<s.size();i++){
        ret[i]=dict[s[i]];
      }
      return ret;
    }
    vector<int>to_int(const string &s){
      auto t=s;
      sort(t.begin(),t.end());
      t.erase(unique(t.begin(),t.end()),t.end());
      return to_int(s,t);
    }
    
    vector<vector<int>>to_int(const vector<string>&s,const string &t){
      regi_str(t);
      vector<vector<int>>ret(s.size(),vector<int>(s[0].size()));
      for(int i=0;i<s.size();i++){
        for(int j=0;j<s[0].size();j++){
          ret[i][j]=dict[s[i][j]];
        }
      }
      return ret;
    }
    vector<vector<int>>to_int(const vector<string>&s){
      string t;
      for(int i=0;i<s.size();i++){
        t+=s[i];
      }
      sort(t.begin(),t.end());t.erase(unique(t.begin(),t.end()),t.end());
      return to_int(s,t);
    }
    string to_str(const vector<int>&s,const string &t){
      regi_int(t);
      string ret;
      for(auto z:s)ret+=dict[z];
      return ret;
    }
    vector<string> to_str(const vector<vector<int>>&s,const string &t){
      regi_int(t);
      vector<string>ret(s.size());
      for(int i=0;i<s.size();i++){
        for(auto z:s[i])ret[i]+=dict[z];
      }
      return ret;
    }
  }
  template< typename T = int >
  struct edge {
    int to;
    T cost;
    int id;
    edge():to(-1),id(-1){};
    edge(int to, T cost = 1, int id = -1):to(to), cost(cost), id(id){}
    operator int() const { return to; }
  };

  template<typename T>
  using Graph = vector<vector<edge<T>>>;
  template<typename T>
  Graph<T>revgraph(const Graph<T> &g){
    Graph<T>ret(g.size());
    for(int i=0;i<g.size();i++){
      for(auto e:g[i]){
        int to = e.to;
        e.to = i;
        ret[to].push_back(e);
      }
    }
    return ret;
  }
  template<typename T>
  Graph<T> readGraph(int n,int m,int indexed=1,bool directed=false,bool weighted=false){
    Graph<T> ret(n);
    for(int es = 0; es < m; es++){
      int u,v;
      T w=1;
      cin>>u>>v;u-=indexed,v-=indexed;
      if(weighted)cin>>w;
      ret[u].emplace_back(v,w,es);
      if(!directed)ret[v].emplace_back(u,w,es);
    }
    return ret;
  }
  template<typename T>
  Graph<T> readParent(int n,int indexed=1,bool directed=true){
    Graph<T>ret(n);
    for(int i=1;i<n;i++){
      int p;cin>>p;
      p-=indexed;
      ret[p].emplace_back(i);
      if(!directed)ret[i].emplace_back(p);
    }
    return ret;
  }
}
using namespace template_tute;

template<typename T>
struct Namori{
  const Graph<T>&g;
  int n;
  int edge_num=0;
  bool directed_forest = false;
  Namori(const Graph<T>&g, bool directed):g(g),n(g.size()){
    directed_forest = directed;
    int edge_num=0;
    for(auto &v:g)edge_num+=v.size();
    build();
  }
  vector<vector<int>>cycle;//連結成分の根となるサイクル サイクルではない場合も
  vector<vector<edge<T>>>cycle_edge;//辺属性
  vector<int>vn,en;//連結成分の頂点数、辺数
  Graph<T>forest;
  vector<int>root;
  vector<int>cycle_number;//頂点が属するサイクル番号 サイクルに属さなければ-1
  void build(){
    dfs_used.assign(n,false);
    dfs_now.assign(n,false);
    dfs_ver.clear();
    dfs_edge.clear();
    root.assign(n,-1);
    for(int i=0;i<n;i++){
      if(dfs_used[i])continue;
      cycle.emplace_back();
      cycle_edge.emplace_back();
      vn.push_back(0);
      en.push_back(0);
      build_dfs(i,-1,cycle.back(),cycle_edge.back());
      if(cycle.back().empty()){
        cycle.back().push_back(i);
      }
    }
    forest.resize(n);
    cycle_number.assign(n,-1);
    for(int i=0;i<cycle.size();i++){
      for(auto v:cycle[i])cycle_number[v]=i;
    }
    dfs_used.assign(n,false);
    for(int i=0;i<n;i++){
      if(cycle_number[i]!=-1)tree_dfs(i,vn[cycle_number[i]],en[cycle_number[i]],i);
    }
    for(int i=0;i<cycle.size();i++)en[i]>>=1;
  }
  void tree_dfs(int pos,int &vn,int &en,int r){
    vn++;
    dfs_used[pos]=true;
    root[pos]=r;
    for(auto e:g[pos]){
      en++;
      if(pos!=r&&dfs_used[e.to]&&!directed_forest)forest[pos].push_back(e);
      if(dfs_used[e.to]||cycle_number[e.to]!=-1)continue;
      forest[pos].push_back(e);
      tree_dfs(e.to,vn,en,r);
    }
  }
  vector<bool>dfs_used;
  vector<int>dfs_ver;
  vector<edge<T>>dfs_edge;
  vector<bool>dfs_now;
  void build_dfs(int pos, int par,vector<int>&cycle,vector<edge<T>>&cycle_edge){
    dfs_used[pos]=true;
    dfs_now[pos]=true;
    dfs_ver.push_back(pos);
    bool multiple_par=false;
    for(auto e:g[pos]){
      if(dfs_now[e.to]&&cycle.empty()&&(e.to!=par||multiple_par)){
        dfs_edge.EB(e);
        rep(i,0,dfs_ver.size()){
          if(!cycle.empty()||dfs_ver[i]==e.to)cycle.push_back(dfs_ver[i]);
          if(!cycle.empty()){
            cycle_edge.push_back(dfs_edge[i]);
          }
        }
        dfs_edge.pop_back();
      }
      if(e.to==par)multiple_par=true;
      if(dfs_used[e.to])continue;
      dfs_edge.push_back(e);
      build_dfs(e.to,pos,cycle,cycle_edge);
      dfs_edge.pop_back();
    }
    dfs_now[pos]=false;
    dfs_ver.pop_back();
  }
};

template<typename T,typename Compare>
struct EraceablePriorityQueue{
  priority_queue<T,vector<T>,Compare>pq, epq;
  void push(T x){pq.push(x);}
  void _erase_top(){
    while(!epq.empty()&&pq.top()==epq.top()){
      pq.pop();
      epq.pop();
    }
  }
  T pop(){
    _erase_top();
    T ret=pq.top();
    pq.pop();
    return ret;
  }
  T top(){
    _erase_top();
    return pq.top();
  }
  void erase(T x){epq.push(x);}
  bool empty(){return pq.size()==epq.size();}
  int size(){return pq.size()-epq.size();}
};
template<typename T>
using MinEraseablePriorityQueue=EraceablePriorityQueue<T,greater<T>>;
template<typename T>
using MaxEraseablePriorityQueue=EraceablePriorityQueue<T,less<T>>;




void solve(){
	ll res=0,buf=0;
  bool judge = true;

  ll n,k;cin>>n>>k;
  vector<int>t(n);
  rep(i,0,n)cin>>t[i];
  Graph<int>g(n);
  vector<int>a(n);
  rep(i,0,n){
    cin>>a[i];
    a[i]--;
    g[i].EB(a[i]);
    g[a[i]].EB(i);
  }
  Namori<int>namori(g,true);
  ll ret=0;
  MaxEraseablePriorityQueue<pair<int,int>>pq;
  ll loopsz=0,arrsz=0;
  vector<vector<int>>loop(n+1);
  vector<vector<int>>arr(n+1);
  auto calc=[&](int x)->ll {
    if(arr[x].size()>=k){
      return arr[x][arr[x].size()-k];
    }
    ll rem=k-arr[x].size()-1;
    if(loop[x].empty())return -INF;
    ll ret=-((ll)rem/(loop[x].size())*loopsz);
    ret+=loop[x][loop[x].size()-1-rem%loop[x].size()];
    return ret;
  };
  auto loop_init=[&](vector<int>v){
    for(auto x:v){
      loop[x].PB(loopsz);
      loopsz++;
    }
    while(!pq.pq.empty())pq.pq.pop();
    while(!pq.epq.empty())pq.epq.pop();
  };
  auto loop_end=[&](vector<int>v){
    loopsz=0;
    for(auto x:v){
      loop[x].pop_back();
    }
    while(!pq.empty()){
      pq.pop();
    }
  };
  auto del=[&](int x){
    auto val=calc(x);
    if(val!=INF)pq.erase(MP(calc(x),x));
  };
  auto ins=[&](int x){
    auto val=calc(x);
    if(val!=INF)pq.push(MP(calc(x),x));
  };
  auto push=[&](int x){
    del(x);
    arr[x].PB(loopsz+arrsz);
    arrsz++;
    ins(x);
  };
  auto pop=[&](int x){
    del(x);
    arr[x].pop_back();
    arrsz--;
    ins(x);
  };
  for(auto cy:namori.cycle){
    if(a[cy[0]]==cy[1%cy.size()]){
      reverse(ALL(cy));
    }
    vector<int>ts;
    for(auto x:cy){
      ts.PB(t[x]);
    }
    loop_init(ts);
    for(auto c:cy){
      auto dfs=[&](auto &&f,int v)->void {
        push(t[v]);
        ret+=ll(v+1)*(pq.top().se);
        for(auto to:namori.forest[v]){
          f(f,to.to);
        }
        pop(t[v]);
      };
      dfs(dfs,c);
      push(t[c]);
    }
    loop_end(ts);
  }
  cout<<ret<<endl;
}

int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  ll res=0,buf=0;
  bool judge = true;
  int T = 1;
  cin>>T;
  while(T--){
    solve();
  }
  return 0;
}
源文件, 语言: C++23

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3612kb

input:

3
5 3
2 2 1 3 3
2 5 1 2 4
5 4
2 2 1 3 3
2 5 1 2 4
3 10
1 2 3
1 3 2

output:

41
45
14

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 69ms
memory: 3988kb

input:

6000
19 48
18 19 18 19 11 9 15 19 12 18 11 18 9 18 9 18 19 11 15
12 14 18 8 1 3 19 5 13 14 15 2 14 5 19 2 19 12 9
15 23
3 1 1 3 6 1 4 1 1 6 6 4 12 4 6
14 1 8 8 6 6 12 14 6 8 5 7 14 2 5
9 140979583
4 5 8 9 2 7 6 8 2
8 9 4 6 9 2 4 7 8
4 976357580
2 3 1 3
2 1 1 4
6 508962809
4 3 4 3 4 4
4 5 4 5 5 6
13 ...

output:

3397
260
254
26
84
759
122
30
1044
1
2493
2422
168
321
298
324
2268
2520
128
228
1107
9
3486
1
796
81
223
272
600
3196
32
495
40
128
140
665
1527
702
68
96
90
288
29
594
16
234
445
2946
140
40
477
1197
19
1542
1082
32
522
672
20
390
32
2204
1870
42
21
885
4
1539
196
420
11
1709
801
720
1
739
40
17
2...

result:

wrong answer 1st lines differ - expected: '3420', found: '3397'
English 繁體中文 简体中文

服务器时间: 2025-02-02 19:57:39 | 开源项目