oj.uz

Submission #1108306

# Submission time Handle Problem Language Result Execution time Memory
1108306 2024-11-03T18:13:56 Z SteveBro Race (IOI11_race) C++17
0 / 100
 18 ms 25424 KB 
#include <bits/stdc++.h>

using namespace std;
int mat[200001][2],ll[200001],p;
const int inf=1e9;
struct ura
{
    int t,s;
    bool ok;
}v[200001];
vector < pair<int,int> > g[200001];
int dfs(int nod, int n)
{
    int sol=-1;
    bool ok=true;
    v[nod].s=1;
    for(auto x : g[nod])
    {
        if(!v[x.first].ok&&v[nod].t!=x.first)
        {
            v[x.first].t=nod;
            sol=max(sol,dfs(x.first,n));
            v[nod].s+=v[x.first].s;
            if(v[x.first].s>n/2)
                ok=false;
        }
    }
    if(n-v[nod].s>n/2)
        ok=false;
    if(ok)
        return nod;
    return max(sol,-1);
}
unordered_map <long long,int> maph;
std :: unordered_map <long long,int> :: iterator it;
int rez=inf;
void dfs1(int nod, long long d, int nrm)
{
    it=maph.find(p-d);
    if(it!=maph.end())
        rez=min(rez,(*it).second+nrm);
    for(auto x : g[nod])
    {
        if(!v[x.first].ok&&x.first!=v[nod].t)
        {
            v[x.first].t=nod;
            dfs1(x.first,d+x.second,nrm+1);
        }
    }
}
void dfs2(int nod, long long d, int nrm)
{
    it=maph.find(d);
    if(it==maph.end())
        maph.insert(make_pair(d,nrm));
    else
        maph.at(d)=min(maph.at(d),nrm);
    for(auto x : g[nod])
    {
        if(!v[x.first].ok&&x.first!=v[nod].t)
        {
            v[x.first].t=nod;
            dfs1(x.first,d+x.second,nrm+1);
        }
    }
}
void divide(int nod, int nr)
{
    if(nr==1)
        return;
    maph.clear();
    maph.insert(make_pair(0,0));
    int ctd=dfs(nod,nr);
    for(auto x : g[ctd])
    {
        if(!v[x.first].ok)
        {
            v[x.first].t=ctd;
            dfs1(x.first,x.second,1);
            dfs2(x.first,x.second,1);
        }
    }
    v[ctd].ok=true;
    for(auto x : g[ctd])
    {
        if(!v[x.first].ok)
        {
            v[x.first].t=ctd;
            divide(x.first,v[x.first].s);
        }
    }
}
int best_path(int n,int k,int h[][2],int l[])
{
    int i;
    for(i=0;i<n-1;i++)
    {
        g[h[i][0]].push_back(make_pair(h[i][1],l[i]));
        g[h[i][1]].push_back(make_pair(h[i][0],l[i]));
    }
    p=k;
    v[1].t=n;
    divide(1,n);
    if(rez==inf)
        rez=-1;
    return rez;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 25424 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 25424 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 25424 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 25424 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -