Submission #165137

#	Time	Username	Problem	Language	Result	Execution time	Memory
165137		Segtree	Wiring (IOI17_wiring)	C++14	100 / 100	289 ms	58384 KiB

wiring

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include"wiring.h"
using namespace std;
typedef long long ll;
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod
#define N 100010
struct qry{
    ll ida,idb,cost;
    bool operator<(const qry&key)const{
	if(this->ida!=key.ida)return this->ida>key.ida;
	if(this->idb!=key.idb)return this->idb>key.idb;
	return this->cost>key.cost;
    };
};
qry qrys(ll p,ll q,ll r){
    qry gen;
    gen.ida=p;
    gen.idb=q;
    gen.cost=r;
    return gen;
}
priority_queue<qry> Q;
unordered_map<ll,ll> dist[N];
unordered_set<ll> ava[N];
void ad(ll x,ll y){
    ava[x].insert(y);
}
bool av(ll x,ll y){
    return ava[x].find(y)!=ava[x].end();
}
ll lastsc[2*N];
ll lastchi[2*N],lastchj[2*N];
ll ruia[N],ruib[N];
ll min_total_length(vector<int> a,vector<int> b){
    ruia[0]=0; for(int i=0;i<a.size();i++)ruia[i+1]=ruia[i]+a[i];
    ruib[0]=0; for(int i=0;i<b.size();i++)ruib[i+1]=ruib[i]+b[i];
    for(int i=0;i<2*N;i++){
	lastsc[i]=1e17;
	lastchi[i]=0;
	lastchj[i]=0;
    }
    Q.push(qrys(0,0,0));
    ad(a.size()-1,b.size()-1);
    ll q=0;
    for(int p=0;p<a.size();p++){
	for(;q<b.size()&&a[p]>b[q];q++){}
	if(q-1>=0)ad(p,q-1);
	if(q<b.size())ad(p,q);
	//cout<<"$"<<p<<" "<<q<<endl;
    }
    q=0;
    for(int p=0;p<b.size();p++){
	for(;q<a.size()&&b[p]>a[q];q++){}
	if(q-1>=0)ad(q-1,p);
	if(q<a.size())ad(q,p);
	//cout<<"$"<<p<<" "<<q<<endl;
    }
    /*
    for(int i=0;i<a.size();i++)for(int j=0;j<b.size();j++){
	if(av(i,j))cout<<"#"<<i<<" "<<j<<endl;
    }*/
    while(!Q.empty()){
	ll i=Q.top().ida;
	ll j=Q.top().idb;
	ll cost=Q.top().cost+abs(a[i]-b[j]);
	Q.pop();
	if(av(i,j)==0)continue;
	if(dist[i].find(j)!=dist[i].end()){
	    if(dist[i][j]<=cost)continue;
	}
	ll base=i-j+N;
	ll ch=lastsc[base]+abs(ruia[i+1]-ruia[lastchi[base]+1]-(ruib[j+1]-ruib[lastchj[base]+1]));
	chmin(cost,ch);
	lastsc[base]=cost;
	lastchi[base]=i,lastchj[base]=j;
	
	if(i+1<a.size()){
	    Q.push(qrys(i+1,j,cost));
	}
	if(j+1<b.size()){
	    Q.push(qrys(i,j+1,cost));
	}
	//cout<<"dist:"<<i<<" "<<j<<" "<<cost<<endl;
	dist[i][j]=cost;
    }
    return dist[a.size()-1][b.size()-1];
}/*
int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    vector<ll> a,b;
    ll n,m; cin>>n>>m;
    for(int i=0;i<n;i++){
	ll x; cin>>x;
	a.push_back(x);
    }
    for(int i=0;i<m;i++){
	ll x; cin>>x;
	b.push_back(x);
    }
    cout<<min_total_length(a,b)<<endl;
}*/

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:44:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     ruia[0]=0; for(int i=0;i<a.size();i++)ruia[i+1]=ruia[i]+a[i];
                            ~^~~~~~~~~
wiring.cpp:45:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     ruib[0]=0; for(int i=0;i<b.size();i++)ruib[i+1]=ruib[i]+b[i];
                            ~^~~~~~~~~
wiring.cpp:54:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int p=0;p<a.size();p++){
                 ~^~~~~~~~~
wiring.cpp:55:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(;q<b.size()&&a[p]>b[q];q++){}
       ~^~~~~~~~~
wiring.cpp:57:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(q<b.size())ad(p,q);
     ~^~~~~~~~~
wiring.cpp:61:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int p=0;p<b.size();p++){
                 ~^~~~~~~~~
wiring.cpp:62:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(;q<a.size()&&b[p]>a[q];q++){}
       ~^~~~~~~~~
wiring.cpp:64:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(q<a.size())ad(q,p);
     ~^~~~~~~~~
wiring.cpp:86:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(i+1<a.size()){
     ~~~^~~~~~~~~
wiring.cpp:89:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(j+1<b.size()){
     ~~~^~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 45 / 45