Submission #563881

#	Time	Username	Problem	Language	Result	Execution time	Memory
563881		errorgorn	Wild Boar (JOI18_wild_boar)	C++17	100 / 100	9373 ms	498480 KiB

wild_boar

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

#define int long long
#define ii pair<int,int>
#define i3 tuple<int,int,int>
#define i4 tuple<int,int,int,int>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n,m,l,q;
struct E{ int to,w,id; };
vector<E> al[2005];

vector<ii> w[2005]; //ok so we store the best 2 guys...
priority_queue<i4,vector<i4>,greater<i4> > pq;

void add(int i,ii val){
  if (w[i][0]==val || w[i][1]==val) return; //prevent from inserting dupes

  //cout<<i<<" "<<val.fi<<" "<<val.se<<endl;
  //rep(x,0,2) cout<<w[i][x].fi<<" "<<w[i][x].se<<endl;

  if (val.fi<w[i][0].fi){
    if (val.fi!=w[i][0].fi){
      swap(w[i][0],w[i][1]);
      pq.push({w[i][1].fi,w[i][1].se,i,1});
    }
    w[i][0]=val;
    pq.push({w[i][0].fi,w[i][0].se,i,0});
  }
  else if (val.fi<w[i][1].fi && w[i][0].se!=val.se){
    w[i][1]=val;
    pq.push({w[i][1].fi,w[i][1].se,i,1});
  }
}

struct dat{
  vector<i3> res;
  dat(){};
  dat (vector<i3> temp){ //pick best 5
    map<int,int> m1,m2;
    set<ii> s;
    sort(all(temp));

    for (auto [w,a,b]:temp){
      if (m1[a]==2 || m2[b]==2 || s.count({a,b})) continue;
      m1[a]++,m2[b]++;
      s.insert({a,b});
      res.pub({w,a,b});
      if (sz(res)==5) break;
    }
  }
};

dat merge(dat i,dat j){
  vector<i3> temp;
  for (auto [w,id1,id2]:i.res) for (auto [w2,id3,id4]:j.res){
    if (id2!=id3) temp.pub({w+w2,id1,id4}); 
  }
  return dat(temp);
}

vector<i3> v[2005];
dat trans[2005][2005];
int arr[100005];

struct node{
  int s,e,m;
  dat val;
  node *l,*r;

  node (int _s,int _e){
    s=_s,e=_e,m=s+e>>1;

    if (s!=e){
      l=new node(s,m);
      r=new node(m+1,e);

      val=merge(l->val,r->val);
    }
    else{
      val=trans[arr[s]][arr[s+1]];
    }
  }

  void update(int i){
    if (s==e) val=trans[arr[i]][arr[i+1]];
    else{
      if (i<=m) l->update(i);
      else r->update(i);
      val=merge(l->val,r->val);
    }
  }
} *root;

signed main(){
  cin.tie(0);
  cout.tie(0);
  cin.sync_with_stdio(false);

  cin>>n>>m>>q>>l;

  int a,b,c;
  rep(x,0,m){
    cin>>a>>b>>c;
    al[a].pub({b,c,x});
    al[b].pub({a,c,x});
  }

  rep(x,1,n+1){
    rep(y,1,n+1) v[y].clear();

    for (auto [y,_W,id]:al[x]){
      rep(x,1,n+1){
        w[x].clear();
        rep(y,1,3) w[x].pub({1e18,-y});
      }
      add(y,{_W,id});

      while (!pq.empty()){
        int W,id,u,pos;
        tie(W,id,u,pos)=pq.top(),pq.pop();
        if (w[u][pos]!=ii(W,id)) continue;

        for (auto [it,w2,id2]:al[u]) if (id!=id2){
          add(it,{W+w2,id2});
        }
      }

      rep(y,1,n+1) for (auto [w,id2]:w[y]) if (w<1e18){
        v[y].pub({w,id,id2});
      }
    }

    rep(y,1,n+1) trans[x][y]=dat(v[y]);
  }

  rep(x,1,l+1) cin>>arr[x];
  root=new node(1,l-1);

  while (q--){
    cin>>a>>b;
    arr[a]=b;

    if (a!=1) root->update(a-1);
    if (a!=l) root->update(a);

    if (root->val.res.empty()) cout<<"-1"<<endl;
    else cout<<get<0>(root->val.res[0])<<endl;
  }
}

Compilation message (stderr)

wild_boar.cpp: In constructor 'node::node(long long int, long long int)':
wild_boar.cpp:88:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |     s=_s,e=_e,m=s+e>>1;
      |                 ~^~

• Subtask 1: 12 / 12
• Subtask 2: 35 / 35
• Subtask 3: 15 / 15
• Subtask 4: 38 / 38