oj.uz

Submission #998241

# Submission time Handle Problem Language Result Execution time Memory
998241 2024-06-13T12:25:01 Z MarwenElarbi Race (IOI11_race) C++17
21 / 100
 3000 ms 178400 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
#define MAX_N 500000
const int nax=2e5+5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

vector<pair<int,int>> adj[nax];
int sz[nax];
bool removed[nax];
vector<vector<pair<ll,pair<ll,int>>>> dist(nax);
vector<map<int,vector<pair<int,int>>>> mp(nax);
set<int> st[nax];
int get_tree_size(int x,int p){
    sz[x]=1;
    for(auto u:adj[x]){
        if(u.fi==p||removed[u.fi]) continue;
        sz[x]+=get_tree_size(u.fi,x);
    }
    return sz[x];
}
int get_centroid(int x,int t_sz,int p){
    for(auto u:adj[x]){
        if(u.fi==p||removed[u.fi]) continue;
        if(sz[u.fi]*2>t_sz){
            return get_centroid(u.fi,t_sz,x);
        }
    }
    return x;
}
void get_dist(int x,int centroid,int p,pair<ll,int> cur){
    for(auto u:adj[x]){
        if(u.fi==p||removed[u.fi]) continue;
        cur.fi+=u.se;
        cur.se++;
        get_dist(u.fi,centroid,x,cur);
        cur.fi-=u.se;
        cur.se--;
    }
    //cout <<x<<" "<<centroid<<" "<<cur.fi<<" "<<cur.se<<endl;
    mp[centroid][cur.fi].pb({x,cur.se});
    dist[x].pb({centroid,cur});
    st[x].insert(centroid);
}
void build(int x){
    int centroid=get_centroid(x,get_tree_size(x,-1),-1);
    for(auto u:adj[centroid]){
        if(removed[u.fi]) continue;
        get_dist(u.fi,centroid,centroid,make_pair(u.se,1));
    }
    removed[centroid]=true;
    for(auto u:adj[centroid]){
        if(removed[u.fi]) continue;
        build(u.fi);
    }
}
int n,k;
int query(int x){
    int ans=1e9;
    if(mp[x].count(k)){
        for (int i = 0; i < mp[x][k].size(); ++i)
        {
            ans=min(ans,mp[x][k][i].se);
        }
    }
    for(int u=0;u<dist[x].size();u++){
        for (int i = 0; i < (int)mp[dist[x][u].fi][k-dist[x][u].se.fi].size(); ++i)
        {
            if(mp[dist[x][u].fi][k-dist[x][u].se.fi][i].fi==x) continue;
            if(u<dist[x].size()-1&&st[mp[dist[x][u].fi][k-dist[x][u].se.fi][i].fi].count(dist[x][u+1].fi)||dist[x][u+1].fi==mp[dist[x][u].fi][k-dist[x][u].se.fi][i].fi||st[mp[dist[x][u].fi][k-dist[x][u].se.fi][i].fi].count(x)) continue;
            ans=min(ans,dist[x][u].se.se+mp[dist[x][u].fi][k-dist[x][u].se.fi][i].se);
            //cout <<" "<<x<<" "<<dist[x][u].fi<<" "<<mp[dist[x][u].fi][k-dist[x][u].se.fi][i].fi<<" "<<ans<<endl;
        }
    }
    return ans;
}
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]].pb({H[i][1],L[i]});
        adj[H[i][1]].pb({H[i][0],L[i]});
    }
    build(0);
    int ans=1e9;
    for (int i = 0; i < n; ++i)
    {
        int cur=query(i);
        ans=min(ans,cur);
    }
    if(ans==1e9) return -1;
    else return ans;
}

Compilation message

race.cpp: In function 'int query(int)':
race.cpp:68:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for (int i = 0; i < mp[x][k].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~~
race.cpp:73:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(int u=0;u<dist[x].size();u++){
      |                 ~^~~~~~~~~~~~~~~
race.cpp:77:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |             if(u<dist[x].size()-1&&st[mp[dist[x][u].fi][k-dist[x][u].se.fi][i].fi].count(dist[x][u+1].fi)||dist[x][u+1].fi==mp[dist[x][u].fi][k-dist[x][u].se.fi][i].fi||st[mp[dist[x][u].fi][k-dist[x][u].se.fi][i].fi].count(x)) continue;
      |                ~^~~~~~~~~~~~~~~~~
race.cpp:77:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   77 |             if(u<dist[x].size()-1&&st[mp[dist[x][u].fi][k-dist[x][u].se.fi][i].fi].count(dist[x][u+1].fi)||dist[x][u+1].fi==mp[dist[x][u].fi][k-dist[x][u].se.fi][i].fi||st[mp[dist[x][u].fi][k-dist[x][u].se.fi][i].fi].count(x)) continue;
      |                ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33368 KB Output is correct
2 Correct 6 ms 33368 KB Output is correct
3 Correct 7 ms 33372 KB Output is correct
4 Correct 6 ms 33116 KB Output is correct
5 Correct 7 ms 33116 KB Output is correct
6 Correct 6 ms 33116 KB Output is correct
7 Correct 6 ms 33416 KB Output is correct
8 Correct 6 ms 33372 KB Output is correct
9 Correct 7 ms 33372 KB Output is correct
10 Correct 6 ms 33372 KB Output is correct
11 Correct 6 ms 33372 KB Output is correct
12 Correct 8 ms 33372 KB Output is correct
13 Correct 7 ms 33372 KB Output is correct
14 Correct 6 ms 33212 KB Output is correct
15 Correct 6 ms 33204 KB Output is correct
16 Correct 7 ms 33372 KB Output is correct
17 Correct 8 ms 33372 KB Output is correct
18 Correct 6 ms 33368 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33368 KB Output is correct
2 Correct 6 ms 33368 KB Output is correct
3 Correct 7 ms 33372 KB Output is correct
4 Correct 6 ms 33116 KB Output is correct
5 Correct 7 ms 33116 KB Output is correct
6 Correct 6 ms 33116 KB Output is correct
7 Correct 6 ms 33416 KB Output is correct
8 Correct 6 ms 33372 KB Output is correct
9 Correct 7 ms 33372 KB Output is correct
10 Correct 6 ms 33372 KB Output is correct
11 Correct 6 ms 33372 KB Output is correct
12 Correct 8 ms 33372 KB Output is correct
13 Correct 7 ms 33372 KB Output is correct
14 Correct 6 ms 33212 KB Output is correct
15 Correct 6 ms 33204 KB Output is correct
16 Correct 7 ms 33372 KB Output is correct
17 Correct 8 ms 33372 KB Output is correct
18 Correct 6 ms 33368 KB Output is correct
19 Correct 6 ms 33112 KB Output is correct
20 Correct 6 ms 33276 KB Output is correct
21 Correct 9 ms 34136 KB Output is correct
22 Correct 10 ms 34652 KB Output is correct
23 Correct 12 ms 34824 KB Output is correct
24 Correct 11 ms 34396 KB Output is correct
25 Correct 9 ms 34396 KB Output is correct
26 Correct 9 ms 34396 KB Output is correct
27 Correct 9 ms 33884 KB Output is correct
28 Correct 9 ms 34560 KB Output is correct
29 Correct 10 ms 34396 KB Output is correct
30 Correct 12 ms 34652 KB Output is correct
31 Correct 11 ms 34560 KB Output is correct
32 Correct 10 ms 34652 KB Output is correct
33 Correct 10 ms 34908 KB Output is correct
34 Correct 9 ms 34908 KB Output is correct
35 Correct 9 ms 34908 KB Output is correct
36 Correct 13 ms 34908 KB Output is correct
37 Correct 10 ms 34652 KB Output is correct
38 Correct 10 ms 34816 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33368 KB Output is correct
2 Correct 6 ms 33368 KB Output is correct
3 Correct 7 ms 33372 KB Output is correct
4 Correct 6 ms 33116 KB Output is correct
5 Correct 7 ms 33116 KB Output is correct
6 Correct 6 ms 33116 KB Output is correct
7 Correct 6 ms 33416 KB Output is correct
8 Correct 6 ms 33372 KB Output is correct
9 Correct 7 ms 33372 KB Output is correct
10 Correct 6 ms 33372 KB Output is correct
11 Correct 6 ms 33372 KB Output is correct
12 Correct 8 ms 33372 KB Output is correct
13 Correct 7 ms 33372 KB Output is correct
14 Correct 6 ms 33212 KB Output is correct
15 Correct 6 ms 33204 KB Output is correct
16 Correct 7 ms 33372 KB Output is correct
17 Correct 8 ms 33372 KB Output is correct
18 Correct 6 ms 33368 KB Output is correct
19 Correct 2580 ms 178296 KB Output is correct
20 Correct 2639 ms 178400 KB Output is correct
21 Execution timed out 3093 ms 162416 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33368 KB Output is correct
2 Correct 6 ms 33368 KB Output is correct
3 Correct 7 ms 33372 KB Output is correct
4 Correct 6 ms 33116 KB Output is correct
5 Correct 7 ms 33116 KB Output is correct
6 Correct 6 ms 33116 KB Output is correct
7 Correct 6 ms 33416 KB Output is correct
8 Correct 6 ms 33372 KB Output is correct
9 Correct 7 ms 33372 KB Output is correct
10 Correct 6 ms 33372 KB Output is correct
11 Correct 6 ms 33372 KB Output is correct
12 Correct 8 ms 33372 KB Output is correct
13 Correct 7 ms 33372 KB Output is correct
14 Correct 6 ms 33212 KB Output is correct
15 Correct 6 ms 33204 KB Output is correct
16 Correct 7 ms 33372 KB Output is correct
17 Correct 8 ms 33372 KB Output is correct
18 Correct 6 ms 33368 KB Output is correct
19 Correct 6 ms 33112 KB Output is correct
20 Correct 6 ms 33276 KB Output is correct
21 Correct 9 ms 34136 KB Output is correct
22 Correct 10 ms 34652 KB Output is correct
23 Correct 12 ms 34824 KB Output is correct
24 Correct 11 ms 34396 KB Output is correct
25 Correct 9 ms 34396 KB Output is correct
26 Correct 9 ms 34396 KB Output is correct
27 Correct 9 ms 33884 KB Output is correct
28 Correct 9 ms 34560 KB Output is correct
29 Correct 10 ms 34396 KB Output is correct
30 Correct 12 ms 34652 KB Output is correct
31 Correct 11 ms 34560 KB Output is correct
32 Correct 10 ms 34652 KB Output is correct
33 Correct 10 ms 34908 KB Output is correct
34 Correct 9 ms 34908 KB Output is correct
35 Correct 9 ms 34908 KB Output is correct
36 Correct 13 ms 34908 KB Output is correct
37 Correct 10 ms 34652 KB Output is correct
38 Correct 10 ms 34816 KB Output is correct
39 Correct 2580 ms 178296 KB Output is correct
40 Correct 2639 ms 178400 KB Output is correct
41 Execution timed out 3093 ms 162416 KB Time limit exceeded
42 Halted 0 ms 0 KB -