oj.uz

Submission #1112850

# Submission time Handle Problem Language Result Execution time Memory
1112850 2024-11-15T03:01:49 Z kiethm07 Race (IOI11_race) C++11
0 / 100
 8 ms 7504 KB 
#include <bits/stdc++.h>
#include <race.h>

#define pii pair<int,int>
#define iii pair<int,pii>
#define fi first
#define se second

#define vi vector<int>
#define all(x) x.begin(),x.end()

#define TEXT "a"

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int inf = 1e9 + 7;
const ld eps = 1e-8;
const double pi = acos(-1);
const int N = 1e5 + 5;

vector<pii> a[N];
int n;
ll k;
map<ll,int> mp[N];
int h[N], sz[N];
ll f[N];

int combine(int u,map<ll,int>& a, map<ll,int>& b){
    ///a.size() >= b.size()
    int res = inf;
    for (pii p : b){
        auto tmp = a.find(k - p.fi + 2 * f[u]);
        if (tmp == a.end()) continue;
        res = min(res, p.second + tmp->second - 2 * h[u]);
//        cout << p.fi << " " << p.se << " " << tmp->fi << " " << tmp->se << " " << h[u] << "\n";
    }
    for (pii p : b){
        if (a.find(p.fi) != a.end()) a[p.fi] = min(a[p.fi], p.se);
        else a[p.fi] = p.se;
    }
    return res;
}

int dfs(int u,int p = -1){
    mp[u][f[u]] = h[u];
    int res = inf;
    for (int i = 0; i < a[u].size(); i++){
        int v = a[u][i].fi;
        int w = a[u][i].se;
        if (v == p) continue;
        h[v] = h[u] + 1;
        f[v] = f[u] + w;
        int tmp = dfs(v,u);
        res = min(res, tmp);
        if (mp[u].size() < mp[v].size()) swap(mp[u], mp[v]);
        res = min(res, combine(u,mp[u],mp[v]));
    }
//    cout << u << " " << res << "\n";
    return res;
}

int best_path(int N,int K,int H[][2],int L[]){
    n = N;
    k = K;
    for (int i = 0; i < n - 1; i++){
        int u = H[i][0] + 1;
        int v = H[i][1] + 1;
        int w = L[i];
        a[u].push_back(pii(v,w));
        a[v].push_back(pii(u,w));
    }
    int res = dfs(1,-1);
    return res;
}

Compilation message

race.cpp: In function 'int dfs(int, int)':
race.cpp:51:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (int i = 0; i < a[u].size(); i++){
      |                     ~~^~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7504 KB Output is correct
2 Correct 8 ms 7504 KB Output is correct
3 Incorrect 8 ms 7504 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7504 KB Output is correct
2 Correct 8 ms 7504 KB Output is correct
3 Incorrect 8 ms 7504 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7504 KB Output is correct
2 Correct 8 ms 7504 KB Output is correct
3 Incorrect 8 ms 7504 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7504 KB Output is correct
2 Correct 8 ms 7504 KB Output is correct
3 Incorrect 8 ms 7504 KB Output isn't correct
4 Halted 0 ms 0 KB -