oj.uz

답안 #669444

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
669444 2022-12-06T13:18:46 Z Bogdan1110 꿈 (IOI13_dreaming) C++14
18 / 100
 70 ms 56928 KB 
#include <bits/stdc++.h>
#include "dreaming.h"
#define FAST {ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
#define FILES {freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);}
#define ll long long
#define ull unsigned long long
#define pqueue priority_queue
#define pb push_back
#define fi first
#define se second
#define ld long double
#define pii pair<int,int>
#define pll pair<long long,long long>
#define all(a) (a).begin(), (a).end()
#define mp make_pair 
using namespace std;
// order_of_key -> # less than k
// find_by_order -> k-th element
// pq max element
 
const double eps = 0.00000001;
const int NMAX = 2000010;
const ll inf = LLONG_MAX/3;
const ll modi = 998244353;
 
int D, maks, mx;
vector<pii>al[NMAX];
int visited[NMAX], dis[NMAX], vv[NMAX];
int maksd,poc;
 
vector<int>vis,nes;
set<int>vektor;
 
void izr() {
    for (auto u : vis) {
        u = dis[u];
        maks = min(maks, u);
    }
}
 
void dfs1(int node, int dist = 0) {
    if (visited[node]) {
        return;
    }
    vv[node] = 1;
    vis.pb(node);
    visited[node] =1;
    if ( dist > maksd ) {
        maksd = dist;
        poc = node;
    }
    for (auto u : al[node] ) {
        dfs1(u.fi, u.se + dist);
    }
}
 
void dfs2(int node, int dist = 0) {
    if (visited[node]) {
        return;
    }
    vis.pb(node);
    visited[node] =1;
    dis[node] = max(dis[node], dist);
    if ( dist > maksd ) {
        maksd = dist;
        poc = node;
    }
    
    for (auto u : al[node] ) {
        dfs2(u.fi, u.se + dist);
    }
}
 
void clrvis() {
    for (auto u : vis) {
        visited[u] = 0;
    }
    vis.clear();
}

void clrdis() {
    for (auto u : vis) {
        dis[u] = 0;
    }
}
 
   
int travelTime(int n,int m,int l,int A[],int B[],int T[]) {
    for (int i = 0 ; i < m; i++) {
        al[A[i]].pb({B[i],T[i]});
        al[B[i]].pb({A[i],T[i]});
    }
    vector<int>r;
    for (int i = 0 ; i < n ; i++ ) {
        if (!vv[i]) {
            maksd = -1;
            dfs1(i);
            clrvis();
		
		 int poc1 = poc;
		   
            
            maksd = -1;
            dfs1(poc);
            
            clrdis();
            clrvis();
 		
 		
		int poc2 = poc;
		D = maksd;
		
		dfs2(poc1);
		clrvis();
		dfs2(poc2);
		
		maks = INT_MAX;
		izr();
		
		clrdis();
		
		//cout << D << ' ' << maks << endl;
						
 		
            r.pb(maks);
        }
    }
 
    //for (auto u : r) cout << u << ' ';
    
 
    sort(all(r));
    int res = r[r.size()-1];
  	if ( r.size() == 1 ) {
      	return res;
    }
  	if ( r.size() == 2 ) {
      	return res + r[0] + l;
    }
  
  	res = max(res, res + r[r.size()-2] + l);
  	res = max(res , r[r.size()-2] + l + r[r.size()-3] + l);
  	
    return res;
}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 70 ms 56928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 47248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 70 ms 56928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 51108 KB Output is correct
2 Correct 42 ms 51028 KB Output is correct
3 Correct 44 ms 51076 KB Output is correct
4 Correct 45 ms 51020 KB Output is correct
5 Correct 48 ms 50964 KB Output is correct
6 Correct 46 ms 51476 KB Output is correct
7 Correct 47 ms 51264 KB Output is correct
8 Correct 44 ms 51016 KB Output is correct
9 Correct 50 ms 51016 KB Output is correct
10 Correct 44 ms 51244 KB Output is correct
11 Correct 22 ms 47188 KB Output is correct
12 Correct 30 ms 49016 KB Output is correct
13 Correct 30 ms 49048 KB Output is correct
14 Correct 29 ms 49104 KB Output is correct
15 Correct 33 ms 49088 KB Output is correct
16 Correct 30 ms 49108 KB Output is correct
17 Correct 30 ms 48944 KB Output is correct
18 Correct 31 ms 49104 KB Output is correct
19 Correct 30 ms 49104 KB Output is correct
20 Correct 26 ms 47284 KB Output is correct
21 Correct 22 ms 47188 KB Output is correct
22 Correct 26 ms 47316 KB Output is correct
23 Correct 30 ms 49032 KB Output is correct

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 47248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 70 ms 56928 KB Output isn't correct
2 Halted 0 ms 0 KB -