oj.uz

Submission #315380

# Submission time Handle Problem Language Result Execution time Memory
315380 2020-10-22T18:54:42 Z tasfiq4 Dreaming (IOI13_dreaming) C++14
0 / 100
 66 ms 12400 KB 
#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=1e9;
	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) 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: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;
      |                                 ^
dreaming.cpp: In function 'pii func(int, int, int)':
dreaming.cpp:35:15: warning: 'n' may be used uninitialized in this function [-Wmaybe-uninitialized]
   35 |  int m=d,m2=0,n,l=1e9;
      |               ^

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 12400 KB Output is correct
2 Correct 62 ms 12144 KB Output is correct
3 Correct 42 ms 10720 KB Output is correct
4 Correct 10 ms 4224 KB Output is correct
5 Incorrect 8 ms 3584 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 12400 KB Output is correct
2 Correct 62 ms 12144 KB Output is correct
3 Correct 42 ms 10720 KB Output is correct
4 Correct 10 ms 4224 KB Output is correct
5 Incorrect 8 ms 3584 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 12400 KB Output is correct
2 Correct 62 ms 12144 KB Output is correct
3 Correct 42 ms 10720 KB Output is correct
4 Correct 10 ms 4224 KB Output is correct
5 Incorrect 8 ms 3584 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 7156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 12400 KB Output is correct
2 Correct 62 ms 12144 KB Output is correct
3 Correct 42 ms 10720 KB Output is correct
4 Correct 10 ms 4224 KB Output is correct
5 Incorrect 8 ms 3584 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 12400 KB Output is correct
2 Correct 62 ms 12144 KB Output is correct
3 Correct 42 ms 10720 KB Output is correct
4 Correct 10 ms 4224 KB Output is correct
5 Incorrect 8 ms 3584 KB Output isn't correct
6 Halted 0 ms 0 KB -