Submission #315544

#	Time	Username	Problem	Language	Result	Execution time	Memory
315544		tasfiq4	Dreaming (IOI13_dreaming)	C++14	0 / 100	52 ms	11640 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int > pii;
typedef long long int lld;
#define pi acos(-1)
#define fr(i,m,n) for(i=m;i<n;i++)
#define fu(i,m,n) for(i=m;i>=n;i--)
#define vec vector<int>
#define pb push_back
#define pp pop_back()
#define ft first
#define sd second
#define all(v) v.begin(),v.end()
#define mom(ara) memset(ara,0,sizeof(ara));
#define m1m(ara) memset(ara,-1,sizeof(ara));
#define endl "\n"
#define eps 1.19209e-07
vector<pii> adj[100010];
int visited[100010];
int mx[100010];
void get_dm(int u,int p)
{
	visited[u]=1;
	mx[u]=0;
	for(auto v:adj[u])
	{
		if(v.ft==p) continue;
		get_dm(v.ft,u);
		mx[u]=max(mx[u],mx[v.ft]+v.sd);
	}
}
pii func(int u,int p,int d)
{
	int m=d,m2=0,n=p,l=0;
	for(auto v:adj[u])
	{
		if(v.ft==p) continue;
		if(mx[v.ft]+v.sd>m)
		{
			m2=m;
			m=mx[v.ft]+v.sd;
			n=v.ft;
			l=v.sd;
		}
		else if(mx[v.ft]+v.sd>m2) m2=mx[v.ft]+v.sd;
	}
	if(m2+l<m && n!=p) return func(n,u,m2+l);
	return {u,m};
}
struct cmp
{
    bool operator()(const pair<int,int> &a,const pair<int,int> &b) const{
    	return a.sd>b.sd;
    }
};
pair<int, int> bfs(int n, int s) {
    vector<int> dis(n+1, -1);
 
    priority_queue<pii,vector<pii>,cmp> q;
    q.push({s,0});
    dis[s] = 0;
    int last = n;
    while (q.size()) {
        int u = q.top().ft;
        q.pop();
 
        for (auto  v: adj[u])
            if (dis[v.ft] == -1) {
                dis[v.ft] = dis[u] + v.sd;
                if(dis[v.ft]>dis[last]) last=v.ft;
                q.push({v.ft,v.sd});
            }
    }
    return {last, dis[last]};
}
bool cp(pii &a,pii &b)
{
    return a.sd>b.sd;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    int i,j,a,b,c,x,y,z,n,m,w,k,t;
    vector<pii> h;
    n=N;m=M;k=L;
    fr(i,0,m)
    {
    	a=A[i];b=B[i];w=T[i];
    	adj[a].pb({b,w});
    	adj[b].pb({a,w});
    }
    fr(i,0,n)
    {
    	if(visited[i]) continue;
    	get_dm(i,-1);
    	h.pb(func(i,-1,0));
    }
    sort(all(h),cp);
    z=0;
    if(h.size()<=1) z=max(z,bfs(n, bfs(n, h[0].ft).first).second);
    else if(h.size()<=2) z=max(z,h[0].sd+h[1].sd+k);
    else z=max(z,h[1].sd+h[2].sd+k); 
    return z;
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:82:11: warning: unused variable 'j' [-Wunused-variable]
   82 |     int i,j,a,b,c,x,y,z,n,m,w,k,t;
      |           ^
dreaming.cpp:82:17: warning: unused variable 'c' [-Wunused-variable]
   82 |     int i,j,a,b,c,x,y,z,n,m,w,k,t;
      |                 ^
dreaming.cpp:82:19: warning: unused variable 'x' [-Wunused-variable]
   82 |     int i,j,a,b,c,x,y,z,n,m,w,k,t;
      |                   ^
dreaming.cpp:82:21: warning: unused variable 'y' [-Wunused-variable]
   82 |     int i,j,a,b,c,x,y,z,n,m,w,k,t;
      |                     ^
dreaming.cpp:82:33: warning: unused variable 't' [-Wunused-variable]
   82 |     int i,j,a,b,c,x,y,z,n,m,w,k,t;
      |                                 ^

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