Submission #897851

#	Time	Username	Problem	Language	Result	Execution time	Memory
897851		Malix	Dreaming (IOI13_dreaming)	C++14	100 / 100	65 ms	25596 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair


int findLeaf(int a,vector<vector<pi>> &c,vi &p,vi &toLeaf,int &i,vi &up,vi &leaf,vi &leafVal){
   // cout<<counter<<" ";
   // counter++;
    if(toLeaf[a]!=-1)return toLeaf[a];
    up[a]=i;
    if(c[a].size()==0){
        toLeaf[a]=0;
        return 0;
    }
    if(c[a].size()<2&&p[a]!=a){
        toLeaf[a]=0;
        return 0;
    }
    for(auto u:c[a]){
        if(u.F==p[a])continue;
        p[u.F]=a;
        toLeaf[a]=max(toLeaf[a],findLeaf(u.F,c,p,toLeaf,i,up,leaf,leafVal)+u.S);
        if(toLeaf[a]==toLeaf[u.F]+u.S){
            leaf[a]=u.F;
            leafVal[a]=u.S;
        }
    } 
    return toLeaf[a];
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    vi p(N,-1);
    vi toLeaf(N,-1);
    vi maxLength(N,0);
    vi up(N);
    vi parents;
    vi leaf,leafVal;
    leaf.resize(N,-1);
    leafVal.resize(N,-1);

    vector<vector<pi>> c(N);
    REP(i,0,M){
        c[A[i]].PB({B[i],T[i]});
        c[B[i]].PB({A[i],T[i]});
    }

    REP(i,0,N){
        if(toLeaf[i]!=-1)continue;
        p[i]=i;parents.PB(i);up[i]=i;
        findLeaf(i,c,p,toLeaf,i,up,leaf,leafVal);
    }
   // cout<<"lol";
    REP(i,0,N){
       // cout<<i<<" "<<c[i].size()<<" ";
       if(c[i].size()==0){
            maxLength[i]=0;
            continue;
       }
       if(c[i].size()==1){
        maxLength[i]=toLeaf[i];
        continue;
       }
        if(c[i].size()<3&&p[i]!=i)continue;
        priority_queue<int> pq;
        for(auto u:c[i]){
            if(p[i]==u.F)continue;
          // if(toLeaf[u]==-1)pq.push(grid[i][u]);
            else pq.push(toLeaf[u.F]+u.S);
        }
        maxLength[i]+=pq.top();
        pq.pop();;
        maxLength[i]+=pq.top();
    }
    
    map<int,pi> m;
    REP(i,0,N){
        if(m.count(up[i])){
            if(m[up[i]].F<maxLength[i]){
                 m[up[i]]=make_pair(maxLength[i],i);
            }
        }
        else{
            m[up[i]]=make_pair(maxLength[i],i);
        }
    }
    
    
    priority_queue<int> maxVals; vi tempVal1,tempVal2;
    for(auto z:parents){
        priority_queue<tuple<int,int,int>> pq2;
        int u=m[z].S;int u2=u;
        tempVal1.clear();tempVal2.clear();
        if(c[u].size()==0){
            maxVals.push(0);
        }
        else if(c[u].size()==1){
            while(leaf[u]!=-1){
                tempVal1.PB(leafVal[u]);
                u=leaf[u];
            }
           // cout<<"lol\n";
            int sum=0;int pos=0;
            while(sum+tempVal1[pos]<=maxLength[u2]/2){
                sum+=tempVal1[pos];
                pos++;
            }
            int sum2=0;
            int ss=tempVal1.size();
           // reverse(tempVal1.begin(),tempVal1.end());
            if(pos<ss){
                sum2=sum+tempVal1[pos];
            }
            //cout<<sum<<" "<<sum2<<"\n";
            sum=min(max(sum,maxLength[u2]-sum),max(sum2,maxLength[u2]-sum2));
            maxVals.push(sum);
            
        }
        else{
            for(auto g:c[u]){
                if(g.F==p[u])continue;
                pq2.push({toLeaf[g.F]+g.S,g.F,g.S});
            }
            int x1=get<1>(pq2.top());
            int xx1=get<2>(pq2.top());
            pq2.pop();
            int x2=get<1>(pq2.top());
            int xx2=get<2>(pq2.top());
            tempVal1.PB(xx1);
            tempVal2.PB(xx2);
            while(leaf[x1]!=-1){
                tempVal1.PB(leafVal[x1]);
                x1=leaf[x1];
            }
            //for(auto y:tempVal1)std::cout<<y<<" ";
            while(leaf[x2]!=-1){
                tempVal2.PB(leafVal[x2]);
                x2=leaf[x2];
            }
            reverse(tempVal1.begin(),tempVal1.end());
            for(auto y:tempVal2)tempVal1.PB(y);
            
            int sum=0;int pos=0;
            while(sum+tempVal1[pos]<=maxLength[u2]/2){
                sum+=tempVal1[pos];
                pos++;
            }
            int sum2=0;
            int ss=tempVal1.size();
           // reverse(tempVal1.begin(),tempVal1.end());
            if(pos<ss){
                sum2=sum+tempVal1[pos];
            }
            //cout<<sum<<" "<<sum2<<"\n";
            sum=min(max(sum,maxLength[u2]-sum),max(sum2,maxLength[u2]-sum2));
            //cout<<sum<<" "<<sum2<<"\n";
            //for(auto tt:tempVal1)cout<<tt<<" ";
           // cout<<"\n";
         //  std::cout<<sum<<" - ";for(auto y:tempVal1)std::cout<<y<<" ";std::cout<<"\n";
            maxVals.push(sum);
        }
    }
    //sort(toLeaf.begin(),toLeaf.end());
   // REP(i,0,N)cout<<toLeaf[i]<<" ";
  // cout<<"\n";
 // REP(i,0,N)cout<<maxLength[i]<<" ";
  // cout<<"\n";
    //for(auto g1:maxVals)cout<<g1<<" ";
   // cout<<"\n";
 // REP(i,0,N)cout<<p[i]<<" ";
   //cout<<"\n";
    
    int r1=maxVals.top();
    maxVals.pop();
    int ans=r1;
    if(!maxVals.empty()){
        int r2=maxVals.top();
        maxVals.pop();
        ans=max(ans,r1+r2+L);
        if(!maxVals.empty()){
            int r3=maxVals.top();
            ans=max(ans,r2+r3+2*L);
        } 
    } 
    
    
   // cout<<r1<<" "<<r2<<" "<<r3<<"\n";
    for(auto z:parents){
        int k1=m[z].F;
        ans=max(ans,k1);
    }
    return ans;

    return 42;
}

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23