Submission #964565

#	Time	Username	Problem	Language	Result	Execution time	Memory
964565		ReLice	Dreaming (IOI13_dreaming)	C++17	47 / 100	229 ms	22208 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define ll int
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define sz size()
#define vll vector<ll>
#define bc back()
#define arr array
#define pll vector<pair<ll,ll>>
using namespace std;
template<class S,class T>
bool chmin(S &a,const T &b) {
	return a>b?(a=b)==b:false;
}
template<class S,class T>
bool chmax(S &a,const T &b) {
	return a<b?(a=b)==b:false;
}
const ll mod=1e9+7;
const ld eps=1e-9;
const ll N=1e5+7;
ll d[N];
vector<set<pair<ll,ll>>> g(N);
ll mx,x;
void dfs(ll v,ll p){
    if(chmax(mx,d[v]))x=v;
    for(auto i : g[v]){
        if(i.fr==p) continue;
        d[i.fr]=d[v]+i.sc;
        dfs(i.fr,v);
    }
}
int travelTime(ll n, ll m, ll l, ll a[], ll b[], ll t[]) {
    ll i,j;
    set<pair<ll,ll>> st;
    for(i=0;i<m;i++){
        a[i]++;
        b[i]++;
        g[a[i]].ins({b[i],t[i]});
        g[b[i]].ins({a[i],t[i]});
    }
    ll ans=0;
    for(i=1;i<=n;i++){
        if(!d[i]){
            mx=0;
            dfs(i,0);
            mx=0;
            d[x]=0;
            dfs(x,0);
            chmax(ans,mx);
        }
    }
    vll v;
    for(i=1;i<=n;i++){
        d[i]=0;
        if(g[i].sz==0){
            v.pb(i);
        }else if(g[i].sz==1){
            st.ins({g[i].begin()->sc,i});
        }
    }
    while(st.sz){
        ll x=st.begin()->sc;
        st.erase(st.begin());
        for(auto i : g[x]){
            g[i.fr].erase(g[i.fr].find({x,i.sc}));
            chmax(d[i.fr],d[x]+i.sc);
            if(g[i.fr].sz==0)v.pb(i.fr);
            else if(g[i.fr].sz==1)st.ins({d[i.fr]+g[i.fr].begin()->sc,i.fr});
        }
        g[x].clear();
    }
    for(i=0;i<v.sz;i++) v[i]=d[v[i]];
    sort(all(v));
    if(v.sz>1)chmax(ans,v.bc+v[v.sz-2]+l);
    return ans;
}/*
signed main(){
    ll n,m,l;
    cin>>n>>m>>l;
    ll a[m],b[m],t[m];
    for(ll i=0;i<m;i++) cin>>a[i];
    for(ll i=0;i<m;i++) cin>>b[i];
    for(ll i=0;i<m;i++) cin>>t[i];
    cout<<travelTime(n,m,l,a,b,t)<<endl;
}*/
/*
12 8 2
0 8 2 5 5 1 1 10
8 2 7 11 1 3 9 6
4 2 4 3 7 1 5 3
*/

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:86:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for(i=0;i<v.sz;i++) v[i]=d[v[i]];
      |              ^
dreaming.cpp:47:10: warning: unused variable 'j' [-Wunused-variable]
   47 |     ll i,j;
      |          ^

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