Submission #489221

#	Time	Username	Problem	Language	Result	Execution time	Memory
489221		NicolaAbusaad2014	Dreaming (IOI13_dreaming)	C++14	100 / 100	82 ms	16548 KiB

dreaming

/**
 * Prof.Nicola
**/
#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;
#define endl "\n"
#define mp make_pair
#define F first
#define S second
#define REP(i,l,r) for(long long i=(l);i<(r);i++)
#define PER(i,l,r) for(long long i=(r)-1;i>=(l);i--)
#define bitl __builtin_clz
#define bitr __builtin_ctz
#define bits __builtin_popcount
const long dx[4]={1,0,-1,0},dz[4]={0,1,0,-1};
const long double pi=3.14159265359;
const long long mod=1e9+7;
long long p(long long x){while(x&(x-1)){x=x&(x-1);}return x;}
long long squared(long long x){return (x*x)%mod;}
long long power(long long x,long long p){if(p==0){return 1;}if(p%2==1){return (power(x,p-1)*x)%mod;}return squared(power(x,p/2));}
long long inv(long long x){return power(x,mod-2);}
long long log(long long x,long long z){if(x<z){return 0;}return 1+log(x/z,z);}
template<class T>void re(T&x){cin>>x;}
template<class T1,class T2> void re(pair<T1,T2>&x){re(x.first);re(x.second);}
template<class T>void re(vector<T>&x){for(long i=0;i<x.size();i++){re(x[i]);}}
template<class T>void re(deque<T>&x){for(long i=0;i<x.size();i++){re(x[i]);}}
template<class T>void out(T x){cout<<x<<" ";}
template<class T1,class T2>void out(pair<T1,T2>x){out(x.first);out(x.second);cout<<endl;}
template<class T>void out(vector<T>x,long l=0,long r=0){if(!r){r=x.size();}for(long i=l;i<r;i++){out(x[i]);}cout<<endl;}
template<class T>void out(deque<T>x,long l=0,long r=0){if(!r){r=x.size();}for(long i=l;i<r;i++){out(x[i]);}cout<<endl;}
template<class T>void out(set<T>x){while(!x.empty()){out(*x.begin());x.erase(*x.begin());}cout<<endl;}
template<class T1,class T2>void out(map<T1,T2>x){while(!x.empty()){out(*x.begin());x.erase(x.begin()->first);}cout<<endl;}
template<class T>void out(queue<T>x){while(!x.empty()){out(x.front());x.pop();}cout<<endl;}
template<class T>void out(priority_queue<T>x){while(!x.empty()){out(x.top());x.pop();}cout<<endl;}
template<class T>void out(stack<T>x){while(!x.empty()){out(x.top());x.pop();}cout<<endl;}
template<class T>T cross(complex<T>x,complex<T>z){return (conj(x)*z).imag();}
template<class T>T dot(complex<T>x,complex<T>z){return (conj(x)*z).real();}
set<long long>::iterator T;
long long vLE(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>x){return -1;}long long z=p(r-l);while(z){if(l+z<=r&&VT[l+z]<=x){l+=z;}z/=2;}return l;}
long long vL(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>=x){return -1;}long long z=p(r-l);while(z){if(l+z<=r&&VT[l+z]<x){l+=z;}z/=2;}return l;}
long long vGE(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>=x){return l;}l=vL(x,VT,l,r);if(l==r){return -1;}return l+1;}
long long vG(long long x,vector<long long>&VT,long l=0,long r=-1){if(r==-1){r=VT.size()-1;}if(VT[l]>x){return l;}l=vLE(x,VT,l,r);if(l==r){return -1;}return l+1;}
long long sLE(long long x,set<long long>&ST){if(ST.count(x)){return x;}if(*ST.begin()>x){return -1;}ST.insert(x);T=ST.find(x);T--;ST.erase(x);return *T;}
long long sL(long long x,set<long long>&ST){if(*ST.begin()>=x){return -1;}if(ST.count(x)){T=ST.find(x);T--;return *T;}ST.insert(x);T=ST.find(x);T--;ST.erase(x);return *T;}
long long sGE(long long x,set<long long>&ST){if(ST.count(x)){return x;}if(*ST.rbegin()<x){return -1;}ST.insert(x);T=ST.find(x);T++;ST.erase(x);return *T;}
long long sG(long long x,set<long long>&ST){if(*ST.rbegin()<=x){return -1;}if(ST.count(x)){T=ST.find(x);T++;return *T;}ST.insert(x);T=ST.find(x);T++;ST.erase(x);return *T;}
vector<vector<pair<int,int> > >edges;
vector<bool>vis;
vector<int>path1,path2,child,srt;
int mn=1e9,ans=0;
long solve(long x)
{
    vis[x]=true;
    int z;
    REP(i,0,edges[x].size()){
        if(vis[edges[x][i].F]){
            continue;
        }
        z=solve(edges[x][i].F)+edges[x][i].S;
        if(z>path1[x]){
            path2[x]=path1[x];
            path1[x]=z;
            child[x]=edges[x][i].F;
            continue;
        }
        path2[x]=max(path2[x],z);
    }
    ans=max(ans,path1[x]+path2[x]);
    return path1[x];
}
void solve2(long x,long p,int sum)
{
    mn=min(mn,max(path1[x],sum));
    REP(i,0,edges[x].size()){
        if(edges[x][i].F==p){
            continue;
        }
        if(edges[x][i].F==child[x]){
            solve2(edges[x][i].F,x,max(sum,path2[x])+edges[x][i].S);
            continue;
        }
        solve2(edges[x][i].F,x,max(sum,path1[x])+edges[x][i].S);
    }
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    vis.resize(N);
    edges.resize(N);
    path1.resize(N);
    path2.resize(N);
    child.resize(N);
    vis.resize(N);
    REP(i,0,M){
        edges[A[i]].push_back(mp(B[i],T[i]));
        edges[B[i]].push_back(mp(A[i],T[i]));
    }
    REP(i,0,N){
        if(vis[i]){
            continue;
        }
        mn=1e9;
        solve(i);
        solve2(i,-1,0);
        srt.push_back(mn);
    }
    sort(srt.rbegin(),srt.rend());
    if(srt.size()==1){
        return ans;
    }
    ans=max(ans,srt[0]+srt[1]+L);
    if(srt.size()==2){
        return ans;
    }
    ans=max(ans,srt[1]+srt[2]+(2*L));
    return ans;
}

Compilation message (stderr)

dreaming.cpp: In function 'long int solve(long int)':
dreaming.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
dreaming.cpp:57:5: note: in expansion of macro 'REP'
   57 |     REP(i,0,edges[x].size()){
      |     ^~~
dreaming.cpp: In function 'void solve2(long int, long int, int)':
dreaming.cpp:12:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define REP(i,l,r) for(long long i=(l);i<(r);i++)
      |                                         ^
dreaming.cpp:76:5: note: in expansion of macro 'REP'
   76 |     REP(i,0,edges[x].size()){
      |     ^~~

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