oj.uz

Submission #563881

# Submission time Handle Problem Language Result Execution time Memory
563881 2022-05-18T08:27:39 Z errorgorn Wild Boar (JOI18_wild_boar) C++17
100 / 100
 9373 ms 498480 KB 
#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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 94740 KB Output is correct
2 Correct 51 ms 94808 KB Output is correct
3 Correct 53 ms 94844 KB Output is correct
4 Correct 52 ms 94840 KB Output is correct
5 Correct 51 ms 94948 KB Output is correct
6 Correct 53 ms 94868 KB Output is correct
7 Correct 54 ms 94876 KB Output is correct
8 Correct 52 ms 94796 KB Output is correct
9 Correct 52 ms 94796 KB Output is correct
10 Correct 55 ms 94764 KB Output is correct
11 Correct 51 ms 94884 KB Output is correct
12 Correct 51 ms 94872 KB Output is correct
13 Correct 50 ms 94864 KB Output is correct
14 Correct 52 ms 94860 KB Output is correct
15 Correct 52 ms 94780 KB Output is correct
16 Correct 53 ms 94796 KB Output is correct
17 Correct 53 ms 94800 KB Output is correct
18 Correct 54 ms 94880 KB Output is correct
19 Correct 54 ms 94844 KB Output is correct
20 Correct 51 ms 94808 KB Output is correct
21 Correct 52 ms 94808 KB Output is correct
22 Correct 53 ms 94788 KB Output is correct
23 Correct 52 ms 94812 KB Output is correct
24 Correct 52 ms 94860 KB Output is correct
25 Correct 51 ms 94836 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 94740 KB Output is correct
2 Correct 51 ms 94808 KB Output is correct
3 Correct 53 ms 94844 KB Output is correct
4 Correct 52 ms 94840 KB Output is correct
5 Correct 51 ms 94948 KB Output is correct
6 Correct 53 ms 94868 KB Output is correct
7 Correct 54 ms 94876 KB Output is correct
8 Correct 52 ms 94796 KB Output is correct
9 Correct 52 ms 94796 KB Output is correct
10 Correct 55 ms 94764 KB Output is correct
11 Correct 51 ms 94884 KB Output is correct
12 Correct 51 ms 94872 KB Output is correct
13 Correct 50 ms 94864 KB Output is correct
14 Correct 52 ms 94860 KB Output is correct
15 Correct 52 ms 94780 KB Output is correct
16 Correct 53 ms 94796 KB Output is correct
17 Correct 53 ms 94800 KB Output is correct
18 Correct 54 ms 94880 KB Output is correct
19 Correct 54 ms 94844 KB Output is correct
20 Correct 51 ms 94808 KB Output is correct
21 Correct 52 ms 94808 KB Output is correct
22 Correct 53 ms 94788 KB Output is correct
23 Correct 52 ms 94812 KB Output is correct
24 Correct 52 ms 94860 KB Output is correct
25 Correct 51 ms 94836 KB Output is correct
26 Correct 57 ms 94948 KB Output is correct
27 Correct 90 ms 116420 KB Output is correct
28 Correct 86 ms 115652 KB Output is correct
29 Correct 295 ms 142092 KB Output is correct
30 Correct 321 ms 143700 KB Output is correct
31 Correct 293 ms 144556 KB Output is correct
32 Correct 294 ms 145088 KB Output is correct
33 Correct 290 ms 140404 KB Output is correct
34 Correct 292 ms 140316 KB Output is correct
35 Correct 275 ms 147832 KB Output is correct
36 Correct 308 ms 145460 KB Output is correct
37 Correct 314 ms 141508 KB Output is correct
38 Correct 286 ms 139624 KB Output is correct
39 Correct 330 ms 147836 KB Output is correct
40 Correct 289 ms 139988 KB Output is correct
41 Correct 293 ms 139800 KB Output is correct
42 Correct 305 ms 150772 KB Output is correct
43 Correct 298 ms 140720 KB Output is correct
44 Correct 300 ms 140796 KB Output is correct
45 Correct 222 ms 129480 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 94740 KB Output is correct
2 Correct 51 ms 94808 KB Output is correct
3 Correct 53 ms 94844 KB Output is correct
4 Correct 52 ms 94840 KB Output is correct
5 Correct 51 ms 94948 KB Output is correct
6 Correct 53 ms 94868 KB Output is correct
7 Correct 54 ms 94876 KB Output is correct
8 Correct 52 ms 94796 KB Output is correct
9 Correct 52 ms 94796 KB Output is correct
10 Correct 55 ms 94764 KB Output is correct
11 Correct 51 ms 94884 KB Output is correct
12 Correct 51 ms 94872 KB Output is correct
13 Correct 50 ms 94864 KB Output is correct
14 Correct 52 ms 94860 KB Output is correct
15 Correct 52 ms 94780 KB Output is correct
16 Correct 53 ms 94796 KB Output is correct
17 Correct 53 ms 94800 KB Output is correct
18 Correct 54 ms 94880 KB Output is correct
19 Correct 54 ms 94844 KB Output is correct
20 Correct 51 ms 94808 KB Output is correct
21 Correct 52 ms 94808 KB Output is correct
22 Correct 53 ms 94788 KB Output is correct
23 Correct 52 ms 94812 KB Output is correct
24 Correct 52 ms 94860 KB Output is correct
25 Correct 51 ms 94836 KB Output is correct
26 Correct 57 ms 94948 KB Output is correct
27 Correct 90 ms 116420 KB Output is correct
28 Correct 86 ms 115652 KB Output is correct
29 Correct 295 ms 142092 KB Output is correct
30 Correct 321 ms 143700 KB Output is correct
31 Correct 293 ms 144556 KB Output is correct
32 Correct 294 ms 145088 KB Output is correct
33 Correct 290 ms 140404 KB Output is correct
34 Correct 292 ms 140316 KB Output is correct
35 Correct 275 ms 147832 KB Output is correct
36 Correct 308 ms 145460 KB Output is correct
37 Correct 314 ms 141508 KB Output is correct
38 Correct 286 ms 139624 KB Output is correct
39 Correct 330 ms 147836 KB Output is correct
40 Correct 289 ms 139988 KB Output is correct
41 Correct 293 ms 139800 KB Output is correct
42 Correct 305 ms 150772 KB Output is correct
43 Correct 298 ms 140720 KB Output is correct
44 Correct 300 ms 140796 KB Output is correct
45 Correct 222 ms 129480 KB Output is correct
46 Correct 225 ms 102036 KB Output is correct
47 Correct 2149 ms 185524 KB Output is correct
48 Correct 2823 ms 230708 KB Output is correct
49 Correct 3441 ms 272348 KB Output is correct
50 Correct 3435 ms 277764 KB Output is correct
51 Correct 3433 ms 278716 KB Output is correct
52 Correct 3677 ms 303216 KB Output is correct
53 Correct 3635 ms 302480 KB Output is correct
54 Correct 3653 ms 302172 KB Output is correct
55 Correct 3654 ms 299320 KB Output is correct
56 Correct 3942 ms 323056 KB Output is correct
57 Correct 4188 ms 348472 KB Output is correct
58 Correct 4452 ms 368048 KB Output is correct
59 Correct 4786 ms 391408 KB Output is correct
60 Correct 5016 ms 413584 KB Output is correct
61 Correct 5243 ms 437080 KB Output is correct
62 Correct 5520 ms 464780 KB Output is correct
63 Correct 5679 ms 495172 KB Output is correct
64 Correct 3750 ms 374688 KB Output is correct
65 Correct 3770 ms 374752 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 94740 KB Output is correct
2 Correct 51 ms 94808 KB Output is correct
3 Correct 53 ms 94844 KB Output is correct
4 Correct 52 ms 94840 KB Output is correct
5 Correct 51 ms 94948 KB Output is correct
6 Correct 53 ms 94868 KB Output is correct
7 Correct 54 ms 94876 KB Output is correct
8 Correct 52 ms 94796 KB Output is correct
9 Correct 52 ms 94796 KB Output is correct
10 Correct 55 ms 94764 KB Output is correct
11 Correct 51 ms 94884 KB Output is correct
12 Correct 51 ms 94872 KB Output is correct
13 Correct 50 ms 94864 KB Output is correct
14 Correct 52 ms 94860 KB Output is correct
15 Correct 52 ms 94780 KB Output is correct
16 Correct 53 ms 94796 KB Output is correct
17 Correct 53 ms 94800 KB Output is correct
18 Correct 54 ms 94880 KB Output is correct
19 Correct 54 ms 94844 KB Output is correct
20 Correct 51 ms 94808 KB Output is correct
21 Correct 52 ms 94808 KB Output is correct
22 Correct 53 ms 94788 KB Output is correct
23 Correct 52 ms 94812 KB Output is correct
24 Correct 52 ms 94860 KB Output is correct
25 Correct 51 ms 94836 KB Output is correct
26 Correct 57 ms 94948 KB Output is correct
27 Correct 90 ms 116420 KB Output is correct
28 Correct 86 ms 115652 KB Output is correct
29 Correct 295 ms 142092 KB Output is correct
30 Correct 321 ms 143700 KB Output is correct
31 Correct 293 ms 144556 KB Output is correct
32 Correct 294 ms 145088 KB Output is correct
33 Correct 290 ms 140404 KB Output is correct
34 Correct 292 ms 140316 KB Output is correct
35 Correct 275 ms 147832 KB Output is correct
36 Correct 308 ms 145460 KB Output is correct
37 Correct 314 ms 141508 KB Output is correct
38 Correct 286 ms 139624 KB Output is correct
39 Correct 330 ms 147836 KB Output is correct
40 Correct 289 ms 139988 KB Output is correct
41 Correct 293 ms 139800 KB Output is correct
42 Correct 305 ms 150772 KB Output is correct
43 Correct 298 ms 140720 KB Output is correct
44 Correct 300 ms 140796 KB Output is correct
45 Correct 222 ms 129480 KB Output is correct
46 Correct 225 ms 102036 KB Output is correct
47 Correct 2149 ms 185524 KB Output is correct
48 Correct 2823 ms 230708 KB Output is correct
49 Correct 3441 ms 272348 KB Output is correct
50 Correct 3435 ms 277764 KB Output is correct
51 Correct 3433 ms 278716 KB Output is correct
52 Correct 3677 ms 303216 KB Output is correct
53 Correct 3635 ms 302480 KB Output is correct
54 Correct 3653 ms 302172 KB Output is correct
55 Correct 3654 ms 299320 KB Output is correct
56 Correct 3942 ms 323056 KB Output is correct
57 Correct 4188 ms 348472 KB Output is correct
58 Correct 4452 ms 368048 KB Output is correct
59 Correct 4786 ms 391408 KB Output is correct
60 Correct 5016 ms 413584 KB Output is correct
61 Correct 5243 ms 437080 KB Output is correct
62 Correct 5520 ms 464780 KB Output is correct
63 Correct 5679 ms 495172 KB Output is correct
64 Correct 3750 ms 374688 KB Output is correct
65 Correct 3770 ms 374752 KB Output is correct
66 Correct 230 ms 136552 KB Output is correct
67 Correct 706 ms 129108 KB Output is correct
68 Correct 2225 ms 226968 KB Output is correct
69 Correct 2405 ms 230612 KB Output is correct
70 Correct 2565 ms 249372 KB Output is correct
71 Correct 6420 ms 187876 KB Output is correct
72 Correct 7163 ms 237680 KB Output is correct
73 Correct 7409 ms 307288 KB Output is correct
74 Correct 7357 ms 308800 KB Output is correct
75 Correct 7397 ms 305412 KB Output is correct
76 Correct 7703 ms 271064 KB Output is correct
77 Correct 7704 ms 281988 KB Output is correct
78 Correct 7620 ms 282144 KB Output is correct
79 Correct 7813 ms 351332 KB Output is correct
80 Correct 8045 ms 375196 KB Output is correct
81 Correct 8800 ms 378816 KB Output is correct
82 Correct 8378 ms 417972 KB Output is correct
83 Correct 9373 ms 444152 KB Output is correct
84 Correct 8947 ms 498480 KB Output is correct
85 Correct 6121 ms 376684 KB Output is correct