Submission #563864

#	Time	Username	Problem	Language	Result	Execution time	Memory
563864		errorgorn	Wild Boar (JOI18_wild_boar)	C++17	100 / 100	9764 ms	499916 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:16: 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