oj.uz

Submission #126249

# Submission time Handle Problem Language Result Execution time Memory
126249 2019-07-07T10:18:11 Z ksmzzang2003 Race (IOI11_race) C++14
0 / 100
 21 ms 8956 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;
vector <int> usecheck;
int dfs1(int now,int prev)
{
    sz[now]  =0;
    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)
{
    dfs1(now,-1);
    int cen = find_cen(now,-1);
    memset(check,-1,sizeof(check));
    //for(int &it:usecheck) check[it] = -1;
check[0] = 0;
        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:17:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<adj[now].size();i++)
                 ~^~~~~~~~~~~~~~~~
race.cpp:20:13: warning: unused variable 'cost' [-Wunused-variable]
         int cost = adj[now][i].second;
             ^~~~
race.cpp:16: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:31:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<adj[now].size();i++)
                 ~^~~~~~~~~~~~~~~~
race.cpp:34: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:49: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:75:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<adj[cen].size();i++)
                 ~^~~~~~~~~~~~~~~~
race.cpp:78: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 20 ms 8952 KB Output is correct
2 Correct 20 ms 8952 KB Output is correct
3 Correct 20 ms 8952 KB Output is correct
4 Correct 20 ms 8952 KB Output is correct
5 Correct 20 ms 8952 KB Output is correct
6 Correct 20 ms 8952 KB Output is correct
7 Correct 20 ms 8952 KB Output is correct
8 Correct 20 ms 8956 KB Output is correct
9 Correct 20 ms 8952 KB Output is correct
10 Correct 20 ms 8952 KB Output is correct
11 Correct 20 ms 8956 KB Output is correct
12 Correct 20 ms 8952 KB Output is correct
13 Correct 20 ms 8952 KB Output is correct
14 Correct 20 ms 8952 KB Output is correct
15 Correct 21 ms 8952 KB Output is correct
16 Correct 20 ms 8952 KB Output is correct
17 Incorrect 20 ms 8952 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8952 KB Output is correct
2 Correct 20 ms 8952 KB Output is correct
3 Correct 20 ms 8952 KB Output is correct
4 Correct 20 ms 8952 KB Output is correct
5 Correct 20 ms 8952 KB Output is correct
6 Correct 20 ms 8952 KB Output is correct
7 Correct 20 ms 8952 KB Output is correct
8 Correct 20 ms 8956 KB Output is correct
9 Correct 20 ms 8952 KB Output is correct
10 Correct 20 ms 8952 KB Output is correct
11 Correct 20 ms 8956 KB Output is correct
12 Correct 20 ms 8952 KB Output is correct
13 Correct 20 ms 8952 KB Output is correct
14 Correct 20 ms 8952 KB Output is correct
15 Correct 21 ms 8952 KB Output is correct
16 Correct 20 ms 8952 KB Output is correct
17 Incorrect 20 ms 8952 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8952 KB Output is correct
2 Correct 20 ms 8952 KB Output is correct
3 Correct 20 ms 8952 KB Output is correct
4 Correct 20 ms 8952 KB Output is correct
5 Correct 20 ms 8952 KB Output is correct
6 Correct 20 ms 8952 KB Output is correct
7 Correct 20 ms 8952 KB Output is correct
8 Correct 20 ms 8956 KB Output is correct
9 Correct 20 ms 8952 KB Output is correct
10 Correct 20 ms 8952 KB Output is correct
11 Correct 20 ms 8956 KB Output is correct
12 Correct 20 ms 8952 KB Output is correct
13 Correct 20 ms 8952 KB Output is correct
14 Correct 20 ms 8952 KB Output is correct
15 Correct 21 ms 8952 KB Output is correct
16 Correct 20 ms 8952 KB Output is correct
17 Incorrect 20 ms 8952 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8952 KB Output is correct
2 Correct 20 ms 8952 KB Output is correct
3 Correct 20 ms 8952 KB Output is correct
4 Correct 20 ms 8952 KB Output is correct
5 Correct 20 ms 8952 KB Output is correct
6 Correct 20 ms 8952 KB Output is correct
7 Correct 20 ms 8952 KB Output is correct
8 Correct 20 ms 8956 KB Output is correct
9 Correct 20 ms 8952 KB Output is correct
10 Correct 20 ms 8952 KB Output is correct
11 Correct 20 ms 8956 KB Output is correct
12 Correct 20 ms 8952 KB Output is correct
13 Correct 20 ms 8952 KB Output is correct
14 Correct 20 ms 8952 KB Output is correct
15 Correct 21 ms 8952 KB Output is correct
16 Correct 20 ms 8952 KB Output is correct
17 Incorrect 20 ms 8952 KB Output isn't correct
18 Halted 0 ms 0 KB -