Submission #1103482

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103482		ezzzay	Nile (IOI24_nile)	C++17	82 / 100	76 ms	15360 KiB

nile

#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define ll long long
const int N=3e5+5;
int par[N];
int sbtr[N];
int H;
void init(int n){
	H=2*n;
	for(int i=0;i<n;i++){
		par[i]=i;
		sbtr[i]=1;
	}
}
int find(int x){
	if(par[x]==x)return x;
	return par[x]=find(par[x]);
}
void unite(int x, int y){
	int px=find(x),py=find(y);
	if(px==py)return;
	if(sbtr[py]>sbtr[px])swap(px,py);
	int a=sbtr[px],b=sbtr[py];
	sbtr[px]+=sbtr[py];
	par[py]=px;
	if(a%2 and b%2 )H-=2;
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
                                       std::vector<int> B, std::vector<int> E) {   
								                  
	init(int(W.size()));                 	
    int q = (int)E.size();
    int n = W.size();
    if(q<=5){
    	  vector<ll>ans;
    vector<pair<ll,ll> >v;
    for(int i=0;i<n;i++){
    	v.pb({W[i],i});
	}
	sort(v.begin(),v.end());
	
	for(int f=0;f<q;f++){
		ll d=E[f];
		vector<vector<ll> > dp ( n+5 , vector<ll> (2)); 
		for(int i=1;i<=n;i++){
			dp[i][0]=1e17;
			dp[i][1]=1e17;
		}
		for(int i=0;i<n;i++){
			int a,b,c;
			a=v[i].ss;
			if(i>0)b=v[i-1].ss;
			if(i>1)c=v[i-2].ss;
			if(i>0) {
				if(abs(W[a]-W[b])<=d) dp[i+1][1]=min(dp[i+1][1],dp[i][0]-A[b]+B[b]+B[a]);
			}
			if(i>1) {
				if(abs(W[a]-W[c])<=d) dp[i+1][1]=min(dp[i+1][1],dp[i-1][0]-A[c]+B[c]+B[a]+A[b]);
			}
			dp[i+1][0]=min(dp[i+1][0],min(dp[i][1],dp[i][0])+A[a]);
		}
		ans.pb(min(dp[n][0],dp[n][1]));
	}
	return ans;
	}
    vector<ll>ans(q);
    vector<pair<ll,ll> >v;
    vector<pair<ll, pair<int,int> > >vc;
    for(int i=0;i<n;i++){
    	v.pb({W[i],i});
	}
	sort(v.begin(),v.end());
	for(int i=1;i<n;i++){
		int x=abs(v[i].ff-v[i-1].ff);
		int a=v[i-1].ss,b=v[i].ss;
		vc.pb({x,{a,b}});
	}
	sort(vc.begin(),vc.end());
	int idx=0;
	vector<pair<int,int>>vec;
	for(int i=0;i<q;i++){
		vec.pb({E[i],i});
	}
	sort(vec.begin(),vec.end());
	
	for(int f=0;f<q;f++){
		ll d=vec[f].ff;
		int k=vec[f].ss;
		while(vc[idx].ff<=d and idx<vc.size()){
			int a=vc[idx].ss.ff,b=vc[idx].ss.ss;
			unite(a,b);
			idx++;
		}
		ans[k]=H;
	}
	return ans;
}

Compilation message (stderr)

nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:92:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |   while(vc[idx].ff<=d and idx<vc.size()){
      |                           ~~~^~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15
• Subtask 7: 0 / 18