oj.uz

Submission #315546

# Submission time Handle Problem Language Result Execution time Memory
315546 2020-10-23T04:07:10 Z tasfiq4 Dreaming (IOI13_dreaming) C++14
18 / 100
 53 ms 11256 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=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);
    if(h.size()>1) z=max(z,h[0].sd+h[1].sd+k);
    if(h.size()>2) z=max(z,h[1].sd+h[2].sd+2*k); 
    return z;
}

Compilation message

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.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 6392 KB Output is correct
2 Correct 28 ms 6852 KB Output is correct
3 Correct 28 ms 6776 KB Output is correct
4 Correct 36 ms 6948 KB Output is correct
5 Correct 32 ms 6784 KB Output is correct
6 Correct 30 ms 7548 KB Output is correct
7 Correct 30 ms 7040 KB Output is correct
8 Correct 28 ms 6784 KB Output is correct
9 Correct 26 ms 6772 KB Output is correct
10 Correct 29 ms 6908 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 8 ms 4600 KB Output is correct
13 Correct 9 ms 4728 KB Output is correct
14 Correct 8 ms 4600 KB Output is correct
15 Correct 9 ms 4600 KB Output is correct
16 Correct 9 ms 4632 KB Output is correct
17 Correct 8 ms 4472 KB Output is correct
18 Correct 9 ms 4728 KB Output is correct
19 Correct 8 ms 4600 KB Output is correct
20 Correct 2 ms 2688 KB Output is correct
21 Correct 2 ms 2688 KB Output is correct
22 Correct 2 ms 2816 KB Output is correct
23 Correct 8 ms 4600 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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