oj.uz

Submission #129559

# Submission time Handle Problem Language Result Execution time Memory
129559 2019-07-12T14:12:41 Z arnold518 Race (IOI11_race) C++14
0 / 100
 10 ms 9080 KB 
#include "race.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;
const int MAXK = 1e6;
const int INF = 987654321;

int N, K, ans=987654321;
vector<pii> adj[MAXN+10];

int sz[MAXN+10];
bool del[MAXN+10];
int M[MAXK+10];

void getsz(int now, int bef)
{
    sz[now]=1;
    for(pii nxt : adj[now])
    {
        if(del[nxt.first]) continue;
        if(nxt.first==bef) continue;
        getsz(nxt.first, now);
        sz[now]+=sz[nxt.first];
    }
}

int getcen(int now, int bef, int tot)
{
    for(pii nxt : adj[now])
    {
        if(del[nxt.first]) continue;
        if(nxt.first==bef) continue;
        if(tot/2<sz[nxt.first]) return getcen(nxt.first, now, tot);
    }
    return now;
}

void dfs(int now, int bef, int dep, int len, vector<pii>& V)
{
    V.push_back({len, dep});

    for(pii nxt : adj[now])
    {
        if(del[nxt.first]) continue;
        if(nxt.first==bef) continue;
        if(len+nxt.second>K) continue;
        dfs(nxt.first, now, dep+1, len+nxt.second, V);
    }
}

void decomp(int now)
{
    int i, j;
    getsz(now, now);
    now=getcen(now, now, sz[now]);
    del[now]=true;
    vector<int> change;

    for(pii nxt : adj[now])
    {
        if(del[nxt.first]) continue;
        vector<pii> V;
        dfs(nxt.first, nxt.first, 1, nxt.second, V);

        for(i=0; i<V.size(); i++)
        {
            int len=V[i].first, dep=V[i].second;
            change.push_back(len);
            ans=min(ans, M[K-len]+dep);
        }

        for(i=0; i<V.size(); i++)
        {
            int len=V[i].first, dep=V[i].second;
            M[len]=min(M[len], dep);
        }
    }

    for(i=0; i<change.size(); i++) M[change[i]]=INF;

    for(pii nxt : adj[now])
    {
        if(del[nxt.first]) continue;
        decomp(nxt.first);
    }
}

int best_path(int NN, int KK, int HH[][2], int LL[])
{
    int i, j;
    N=NN; K=KK;
    for(i=0; i+1<N; i++)
    {
        int u=HH[i][0], v=HH[i][1], w=LL[i];
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    for(i=0; i<=1000000; i++) M[i]=INF;

    decomp(0);
    if(ans==INF) ans=-1;
    return ans;
}

Compilation message

race.cpp: In function 'void decomp(int)':
race.cpp:70:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0; i<V.size(); i++)
                  ~^~~~~~~~~
race.cpp:77:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0; i<V.size(); i++)
                  ~^~~~~~~~~
race.cpp:84:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<change.size(); i++) M[change[i]]=INF;
              ~^~~~~~~~~~~~~~
race.cpp:58:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:95:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^

Subtask #1
0 / 9.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 57.0

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