oj.uz

Submission #1090484

# Submission time Handle Problem Language Result Execution time Memory
1090484 2024-09-18T12:04:34 Z simona1230 Race (IOI11_race) C++17
31 / 100
 3000 ms 53036 KB 
#include "race.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> v[200001],w[200001];
int ans=200000;

void add(int i,int j,int k)
{
    v[i].push_back(j);
    v[j].push_back(i);
    w[i].push_back(k);
    w[j].push_back(k);
}

int n,k;

int all;
int sz[200001];
int mark[200001];

void prec(int i,int p)
{
    sz[i]=1;
    for(int j=0;j<v[i].size();j++)
    {
        int nb=v[i][j];
        if(nb==p||mark[nb])continue;

        prec(nb,i);
        sz[i]+=sz[nb];
    }
}

int centroid(int i,int p)
{
    for(int j=0;j<v[i].size();j++)
    {
        int nb=v[i][j];
        if(nb==p||mark[nb])continue;

        if(sz[nb]>all/2)return centroid(nb,i);
    }

    return i;
}

map<int,int> mp;
vector<pair<int,int> > ext;

void dfs(int i,int p,int cnt,int wg)
{
    if(wg>k)return;

    if(wg==k)ans=min(ans,cnt);
    else
    {
        int wg2=k-wg;
        //cout<<wg2<<" + "<<mp[wg2]<<endl;
        ans=min(ans,cnt+mp[wg2]);
    }

    //cout<<i<<" "<<wg<<endl;

    ext.push_back({wg,cnt});

    for(int j=0;j<v[i].size();j++)
    {
        int nb=v[i][j];
        if(nb==p||mark[nb])continue;

        dfs(nb,i,cnt+1,wg+w[i][j]);
    }
}

void solve(int beg)
{
    prec(beg,-1);
    all=sz[beg];
    //cout<<all<<endl;
    int c=centroid(beg,-1);
    //cout<<"! "<<c<<endl;

    for(int i=1;i<=k;i++)
        mp[i]=n;
    mark[c]=1;

    for(int i=0;i<v[c].size();i++)
    {
        int nb=v[c][i];
        if(mark[nb])continue;

        //cout<<c<<" "<<nb<<endl;
        dfs(nb,-1,1,w[c][i]);

        for(int j=0;j<ext.size();j++)
        {
            //cout<<"= "<<ext[j].first<<endl;
            mp[ext[j].first]=min(mp[ext[j].first],ext[j].second);
        }
        ext.clear();
    }

    for(int i=0;i<v[c].size();i++)
    {
        int nb=v[c][i];
        if(!mark[nb])solve(nb);
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    n=N;
    k=K;

    for(int i=0;i<n-1;i++)
        add(H[i][0],H[i][1],L[i]);

    solve(0);

    if(ans>=n)return -1;
    return ans;
}

Compilation message

race.cpp: In function 'void prec(int, int)':
race.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int j=0;j<v[i].size();j++)
      |                 ~^~~~~~~~~~~~
race.cpp: In function 'int centroid(int, int)':
race.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int j=0;j<v[i].size();j++)
      |                 ~^~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int, int, int)':
race.cpp:67:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int j=0;j<v[i].size();j++)
      |                 ~^~~~~~~~~~~~
race.cpp: In function 'void solve(int)':
race.cpp:88:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for(int i=0;i<v[c].size();i++)
      |                 ~^~~~~~~~~~~~
race.cpp:96:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         for(int j=0;j<ext.size();j++)
      |                     ~^~~~~~~~~~~
race.cpp:104:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |     for(int i=0;i<v[c].size();i++)
      |                 ~^~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 5 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 6 ms 9820 KB Output is correct
5 Correct 6 ms 9844 KB Output is correct
6 Correct 5 ms 9844 KB Output is correct
7 Correct 5 ms 9820 KB Output is correct
8 Correct 5 ms 9820 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 5 ms 9820 KB Output is correct
11 Correct 6 ms 9816 KB Output is correct
12 Correct 5 ms 9820 KB Output is correct
13 Correct 4 ms 9816 KB Output is correct
14 Correct 4 ms 9820 KB Output is correct
15 Correct 4 ms 9820 KB Output is correct
16 Correct 4 ms 9820 KB Output is correct
17 Correct 6 ms 9812 KB Output is correct
18 Correct 4 ms 9820 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 5 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 6 ms 9820 KB Output is correct
5 Correct 6 ms 9844 KB Output is correct
6 Correct 5 ms 9844 KB Output is correct
7 Correct 5 ms 9820 KB Output is correct
8 Correct 5 ms 9820 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 5 ms 9820 KB Output is correct
11 Correct 6 ms 9816 KB Output is correct
12 Correct 5 ms 9820 KB Output is correct
13 Correct 4 ms 9816 KB Output is correct
14 Correct 4 ms 9820 KB Output is correct
15 Correct 4 ms 9820 KB Output is correct
16 Correct 4 ms 9820 KB Output is correct
17 Correct 6 ms 9812 KB Output is correct
18 Correct 4 ms 9820 KB Output is correct
19 Correct 4 ms 9820 KB Output is correct
20 Correct 4 ms 9652 KB Output is correct
21 Correct 13 ms 9816 KB Output is correct
22 Execution timed out 3027 ms 53036 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 5 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 6 ms 9820 KB Output is correct
5 Correct 6 ms 9844 KB Output is correct
6 Correct 5 ms 9844 KB Output is correct
7 Correct 5 ms 9820 KB Output is correct
8 Correct 5 ms 9820 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 5 ms 9820 KB Output is correct
11 Correct 6 ms 9816 KB Output is correct
12 Correct 5 ms 9820 KB Output is correct
13 Correct 4 ms 9816 KB Output is correct
14 Correct 4 ms 9820 KB Output is correct
15 Correct 4 ms 9820 KB Output is correct
16 Correct 4 ms 9820 KB Output is correct
17 Correct 6 ms 9812 KB Output is correct
18 Correct 4 ms 9820 KB Output is correct
19 Correct 238 ms 19628 KB Output is correct
20 Correct 264 ms 19536 KB Output is correct
21 Correct 263 ms 19664 KB Output is correct
22 Correct 256 ms 20032 KB Output is correct
23 Correct 219 ms 19436 KB Output is correct
24 Correct 157 ms 19948 KB Output is correct
25 Correct 214 ms 23556 KB Output is correct
26 Correct 173 ms 27724 KB Output is correct
27 Correct 282 ms 30292 KB Output is correct
28 Correct 435 ms 44772 KB Output is correct
29 Correct 394 ms 43604 KB Output is correct
30 Correct 353 ms 30228 KB Output is correct
31 Correct 365 ms 30360 KB Output is correct
32 Correct 436 ms 30768 KB Output is correct
33 Correct 412 ms 29264 KB Output is correct
34 Correct 316 ms 30036 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 5 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 6 ms 9820 KB Output is correct
5 Correct 6 ms 9844 KB Output is correct
6 Correct 5 ms 9844 KB Output is correct
7 Correct 5 ms 9820 KB Output is correct
8 Correct 5 ms 9820 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 5 ms 9820 KB Output is correct
11 Correct 6 ms 9816 KB Output is correct
12 Correct 5 ms 9820 KB Output is correct
13 Correct 4 ms 9816 KB Output is correct
14 Correct 4 ms 9820 KB Output is correct
15 Correct 4 ms 9820 KB Output is correct
16 Correct 4 ms 9820 KB Output is correct
17 Correct 6 ms 9812 KB Output is correct
18 Correct 4 ms 9820 KB Output is correct
19 Correct 4 ms 9820 KB Output is correct
20 Correct 4 ms 9652 KB Output is correct
21 Correct 13 ms 9816 KB Output is correct
22 Execution timed out 3027 ms 53036 KB Time limit exceeded
23 Halted 0 ms 0 KB -