Submission #347793

#	Time	Username	Problem	Language	Result	Execution time	Memory
347793		tigicha	Dreaming (IOI13_dreaming)	C++17	100 / 100	111 ms	23532 KiB

dreaming

#include"dreaming.h"
#include<bits/stdc++.h>
using namespace std;
int fix[500005], mx, l, ans, k, x, y;
vector<pair<int, int> >v[500005];
vector<int>vec;
stack<int>s;
void dfs(int x, int y, int z){
    fix[x]=1;
    if(mx<z){
    	mx=z;
		l=x;
	}
    for(int i=0; i<v[x].size(); i++)
    if(v[x][i].first==y) continue;
    else dfs(v[x][i].first, x, z+v[x][i].second);
}
void dfs1(int x, int y, int z, int p){
    if(z!=-1 && k==0) s.push(v[z][p].second);
    for(int i=0; i<v[x].size(); i++)
    if(v[x][i].first==z) continue;
    else dfs1(v[x][i].first, y, x, i);
    if(x==y) k=1;
    if(k==0) s.pop();
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
    for(long long i=0; i<M; i++) {
        v[A[i]].push_back({B[i], T[i]});
        v[B[i]].push_back({A[i], T[i]});
    }
    for(long long i=0; i<N; i++){
        if(fix[i]!=0) continue;
        mx=0;
		l=-1;
        dfs(i, l, mx);
        x=l;
        mx=0;
		l=-1;
        dfs(x, l, mx);
        y=l;
        ans=max(ans, mx);
		k=0;
        dfs1(x, y, -1, 0);
		if(s.empty()) vec.push_back(0); 
        x=0;
        while(!s.empty()){
            x+=s.top();
            if(x==mx/2 && mx%2==0){
            	vec.push_back(mx/2);
				break;
			}
            else if(x>mx/2){
                vec.push_back(min(x, max(x-s.top(), mx-x+s.top())));
                break;
            }
            s.pop();
        }
        while(!s.empty()) s.pop();
    }
    sort(vec.begin(), vec.end());
    if(vec.size()>=2) ans=max(ans, vec[vec.size()-1]+vec[vec.size()-2]+L);
    if(vec.size()>=3) ans=max(ans, vec[vec.size()-2]+vec[vec.size()-3]+2*L);
    return ans;
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs(int, int, int)':
dreaming.cpp:14:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for(int i=0; i<v[x].size(); i++)
      |                  ~^~~~~~~~~~~~
dreaming.cpp: In function 'void dfs1(int, int, int, int)':
dreaming.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=0; i<v[x].size(); i++)
      |                  ~^~~~~~~~~~~~

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