Submission #315367

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
315367	2020-10-22T17:55:33 Z	tasfiq4	Dreaming (IOI13_dreaming)	C++14	Compilation error	0 ms	0 KB

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,l;
	for(auto v:adj[u])
	{
		if(v.ft==p) continue;
		if(mx[v.ft]>m)
		{
			m2=m;
			m=mx[v.ft];
			n=v.ft;
			l=v.sd;
		}
		else if(mx[v.ft]>m2) m2=mx[v.ft];
	}
	if(m2+l<m) 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]};
}
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;
    priority_queue<pii,vector<pii>,cmp> 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.push(func(i,-1,0));
    }
    while(h.size()!=1)
    {
        pii u=h.top();
        h.pop();
        pii v=h.top();
        h.pop();
        h.push({u.ft,max(u.sd+k,v,sd)});
    }
    return bfs(n, bfs(n, 0).first).second;

}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:13:12: error: 'second' was not declared in this scope
   13 | #define sd second
      |            ^~~~~~
dreaming.cpp:99:35: note: in expansion of macro 'sd'
   99 |         h.push({u.ft,max(u.sd+k,v,sd)});
      |                                   ^~
dreaming.cpp:99:39: error: no matching function for call to 'std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, cmp>::push(<brace-enclosed initializer list>)'
   99 |         h.push({u.ft,max(u.sd+k,v,sd)});
      |                                       ^
In file included from /usr/include/c++/9/queue:64,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:86,
                 from dreaming.cpp:2:
/usr/include/c++/9/bits/stl_queue.h:627:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(const value_type&) [with _Tp = std::pair<int, int>; _Sequence = std::vector<std::pair<int, int> >; _Compare = cmp; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::pair<int, int>]'
  627 |       push(const value_type& __x)
      |       ^~~~
/usr/include/c++/9/bits/stl_queue.h:627:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::pair<int, int>&'}
  627 |       push(const value_type& __x)
      |            ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/9/bits/stl_queue.h:635:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(std::priority_queue<_Tp, _Sequence, _Compare>::value_type&&) [with _Tp = std::pair<int, int>; _Sequence = std::vector<std::pair<int, int> >; _Compare = cmp; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::pair<int, int>]'
  635 |       push(value_type&& __x)
      |       ^~~~
/usr/include/c++/9/bits/stl_queue.h:635:25: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, cmp>::value_type&&' {aka 'std::pair<int, int>&&'}
  635 |       push(value_type&& __x)
      |            ~~~~~~~~~~~~~^~~
dreaming.cpp:78:11: warning: unused variable 'j' [-Wunused-variable]
   78 |     int i,j,a,b,c,x,y,z,n,m,w,k,t;
      |           ^
dreaming.cpp:78:17: warning: unused variable 'c' [-Wunused-variable]
   78 |     int i,j,a,b,c,x,y,z,n,m,w,k,t;
      |                 ^
dreaming.cpp:78:19: warning: unused variable 'x' [-Wunused-variable]
   78 |     int i,j,a,b,c,x,y,z,n,m,w,k,t;
      |                   ^
dreaming.cpp:78:21: warning: unused variable 'y' [-Wunused-variable]
   78 |     int i,j,a,b,c,x,y,z,n,m,w,k,t;
      |                     ^
dreaming.cpp:78:23: warning: unused variable 'z' [-Wunused-variable]
   78 |     int i,j,a,b,c,x,y,z,n,m,w,k,t;
      |                       ^
dreaming.cpp:78:33: warning: unused variable 't' [-Wunused-variable]
   78 |     int i,j,a,b,c,x,y,z,n,m,w,k,t;
      |                                 ^