oj.uz

Submission #126184

# Submission time Handle Problem Language Result Execution time Memory
126184 2019-07-07T08:21:46 Z ksmzzang2003 Race (IOI11_race) C++14
0 / 100
 27 ms 9848 KB 
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair <int,int> pii;
int N,K,L[200003];
int par[200003],sz[200003];
vector <pii> adj[200003];
int check[1000003];
bool del[200003];
int ans = 1987654321;
vector <pii> lazy;
int dfs1(int now,int prev)
{
    bool reaf=true;
    for(int i=0;i<adj[now].size();i++)
    {
        int next = adj[now][i].first;
        int cost = adj[now][i].second;
        if(next == prev) continue;
        if(del[next]) continue;
        reaf = false;
        sz[now] += dfs1(next,now);
    }
    return ++sz[now];
}

int find_cen(int now,int prev)
{
    for(int i=0;i<adj[now].size();i++)
    {
        int next = adj[now][i].first;
        int cost = adj[now][i].second;
        if(next == prev) continue;
        if(del[next]) continue;
        if(sz[next]*2>sz[now]) return find_cen(next,now);
    }
    return now;
}

int dfs2(int now,int prev,int sum,int depth)
{
    int ret = 1987654321;
    if(sum>K) return 1987654321;
    if(check[K-sum]!=-1) ret= min(ret,depth + check[K-sum]);
    lazy.push_back(pii(sum,depth));
    for(int i=0;i<adj[now].size();i++)
    {
        int next = adj[now][i].first;
        int cost = adj[now][i].second;
        if(next == prev) continue;
        if(del[next]) continue;
        ret = min(ret,dfs2(next,now,sum+cost,depth+1));
        if(sum==0)
        {
            for(pii &it:lazy) check[it.first] = it.second;
            lazy.clear();
        }
    }
    return ret;
}

void g(int now,int prev)
{
    memset(sz,0,sizeof(sz));
    dfs1(now,-1);
    int cen = find_cen(now,-1);
    memset(check,-1,sizeof(check));
    lazy.clear();
    ans = min(ans,dfs2(cen,-1,0,0));
    del[cen] = true;
    for(int i=0;i<adj[cen].size();i++)
    {
        int next = adj[cen][i].first;
        int cost = adj[cen][i].second;
        if(next == prev) continue;
        if(del[next]) continue;
        g(next,now);
    }
}

int best_path(int n, int k, int h[][2], int l[])
{
    N= n ; K = k;
    for(int i=0;i<n-1;i++)
    {
        adj[h[i][0]].push_back(pii(h[i][1],l[i]));
        adj[h[i][1]].push_back(pii(h[i][0],l[i]));
    }
    g(1,-1);
    return (ans>=1987654300)?-1:ans;
}

Compilation message

race.cpp: In function 'int dfs1(int, int)':
race.cpp:15:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<adj[now].size();i++)
                 ~^~~~~~~~~~~~~~~~
race.cpp:18:13: warning: unused variable 'cost' [-Wunused-variable]
         int cost = adj[now][i].second;
             ^~~~
race.cpp:14:10: warning: variable 'reaf' set but not used [-Wunused-but-set-variable]
     bool reaf=true;
          ^~~~
race.cpp: In function 'int find_cen(int, int)':
race.cpp:29:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<adj[now].size();i++)
                 ~^~~~~~~~~~~~~~~~
race.cpp:32:13: warning: unused variable 'cost' [-Wunused-variable]
         int cost = adj[now][i].second;
             ^~~~
race.cpp: In function 'int dfs2(int, int, int, int)':
race.cpp:46:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<adj[now].size();i++)
                 ~^~~~~~~~~~~~~~~~
race.cpp: In function 'void g(int, int)':
race.cpp:71:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<adj[cen].size();i++)
                 ~^~~~~~~~~~~~~~~~
race.cpp:74:13: warning: unused variable 'cost' [-Wunused-variable]
         int cost = adj[cen][i].second;
             ^~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 9720 KB Output is correct
2 Correct 23 ms 9848 KB Output is correct
3 Correct 27 ms 9720 KB Output is correct
4 Correct 23 ms 9720 KB Output is correct
5 Correct 23 ms 9720 KB Output is correct
6 Correct 23 ms 9684 KB Output is correct
7 Correct 23 ms 9720 KB Output is correct
8 Correct 24 ms 9720 KB Output is correct
9 Correct 23 ms 9720 KB Output is correct
10 Correct 23 ms 9720 KB Output is correct
11 Correct 22 ms 9720 KB Output is correct
12 Correct 23 ms 9720 KB Output is correct
13 Correct 23 ms 9720 KB Output is correct
14 Correct 23 ms 9720 KB Output is correct
15 Correct 24 ms 9720 KB Output is correct
16 Correct 24 ms 9720 KB Output is correct
17 Incorrect 22 ms 9732 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 9720 KB Output is correct
2 Correct 23 ms 9848 KB Output is correct
3 Correct 27 ms 9720 KB Output is correct
4 Correct 23 ms 9720 KB Output is correct
5 Correct 23 ms 9720 KB Output is correct
6 Correct 23 ms 9684 KB Output is correct
7 Correct 23 ms 9720 KB Output is correct
8 Correct 24 ms 9720 KB Output is correct
9 Correct 23 ms 9720 KB Output is correct
10 Correct 23 ms 9720 KB Output is correct
11 Correct 22 ms 9720 KB Output is correct
12 Correct 23 ms 9720 KB Output is correct
13 Correct 23 ms 9720 KB Output is correct
14 Correct 23 ms 9720 KB Output is correct
15 Correct 24 ms 9720 KB Output is correct
16 Correct 24 ms 9720 KB Output is correct
17 Incorrect 22 ms 9732 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 9720 KB Output is correct
2 Correct 23 ms 9848 KB Output is correct
3 Correct 27 ms 9720 KB Output is correct
4 Correct 23 ms 9720 KB Output is correct
5 Correct 23 ms 9720 KB Output is correct
6 Correct 23 ms 9684 KB Output is correct
7 Correct 23 ms 9720 KB Output is correct
8 Correct 24 ms 9720 KB Output is correct
9 Correct 23 ms 9720 KB Output is correct
10 Correct 23 ms 9720 KB Output is correct
11 Correct 22 ms 9720 KB Output is correct
12 Correct 23 ms 9720 KB Output is correct
13 Correct 23 ms 9720 KB Output is correct
14 Correct 23 ms 9720 KB Output is correct
15 Correct 24 ms 9720 KB Output is correct
16 Correct 24 ms 9720 KB Output is correct
17 Incorrect 22 ms 9732 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 9720 KB Output is correct
2 Correct 23 ms 9848 KB Output is correct
3 Correct 27 ms 9720 KB Output is correct
4 Correct 23 ms 9720 KB Output is correct
5 Correct 23 ms 9720 KB Output is correct
6 Correct 23 ms 9684 KB Output is correct
7 Correct 23 ms 9720 KB Output is correct
8 Correct 24 ms 9720 KB Output is correct
9 Correct 23 ms 9720 KB Output is correct
10 Correct 23 ms 9720 KB Output is correct
11 Correct 22 ms 9720 KB Output is correct
12 Correct 23 ms 9720 KB Output is correct
13 Correct 23 ms 9720 KB Output is correct
14 Correct 23 ms 9720 KB Output is correct
15 Correct 24 ms 9720 KB Output is correct
16 Correct 24 ms 9720 KB Output is correct
17 Incorrect 22 ms 9732 KB Output isn't correct
18 Halted 0 ms 0 KB -