Submission #1305418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305418		yusifm	Race (IOI11_race)	C++20	21 / 100	165 ms	15484 KiB

race

//pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "race.h"
const int sz=1001,INF=1000000000;
using namespace std;
int res;
vector<int>d(sz);
vector<bool>isSeen(sz);
vector<vector<int>>parent(sz,vector<int>(11)),cnts(sz,vector<int>(sz,0)),dist(sz,vector<int>(sz,INF));
vector<vector<pair<int,int>>>nums;
void dfs(int num)
{
    isSeen[num]=true;
    for(int i=0;i<nums[num].size();i++)
    {
        if(!isSeen[nums[num][i].first])
        {
            parent[nums[num][i].first][0]=num,d[nums[num][i].first]=d[num]+1;
            dfs(nums[num][i].first);
        }
    }
}
int lca(int num1,int num2)
{
    if(d[num1]<d[num2])
    {
        swap(num1,num2);
    }
    for(int i=10;i>=0;i--)
    {
        if(d[num1]-pow(2,i)>=d[num2])
        {
            num1=parent[num1][i];
        }
    }
    if(num1==num2)
    {
        return num1;
    }
    else
    {
        for(int i=10;i>=0;i--)
        {
            if(parent[num1][i]!=parent[num2][i])
            {
                num1=parent[num1][i],num2=parent[num2][i];
            }
        }
        return parent[num1][0];
    }
}
void bfs(int num)
{
    queue<int>numS;
    numS.push(num);
    cnts[num][num]=1;
    while(numS.size()!=0)
    {
        res=numS.front();
        numS.pop();
        for(int i=0;i<nums[res].size();i++)
        {
            if(cnts[num][nums[res][i].first]==0)
            {
                numS.push(nums[res][i].first);
                cnts[num][nums[res][i].first]=cnts[num][res]+1;
            }
        }
    }
}
void dijkstra(int num)
{
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>Pq;
    Pq.push({0,num});
    dist[num][num]=0;
    while(Pq.size()!=0)
    {
        res=Pq.top().second;
        Pq.pop();
        for(int i=0;i<nums[res].size();i++)
        {
            if(dist[num][res]+nums[res][i].second<dist[num][nums[res][i].first])
            {
                Pq.push({dist[num][nums[res][i].first],nums[res][i].first});
                dist[num][nums[res][i].first]=dist[num][res]+nums[res][i].second;
            }
        }
    }
}
int best_path(int n,int m,int nums1[][2],int nums2[])
{
    int anc,cnt,Dist,ans=INF;
    nums.resize(n+1);
    for(int i=0;i<n-1;i++)
    {
        nums[nums1[i][0]+1].push_back({nums1[i][1]+1,nums2[i]}),nums[nums1[i][1]+1].push_back({nums1[i][0]+1,nums2[i]});
    }
    dfs(1);
    for(int i=1;i<=10;i++)
    {
        for(int j=1;j<=n;j++)
        {
            parent[j][i]=parent[parent[j][i-1]][i-1];
        }
    }
    for(int i=1;i<=n;i++)
    {
        bfs(i),dijkstra(i);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            anc=lca(i,j),Dist=dist[anc][i]+dist[anc][j],cnt=cnts[anc][i]+cnts[anc][j]-1;
            if(Dist==m)
            {
                ans=min(ans,cnt-1);
            }
        }
    }
    if(ans==INF)
    {
        ans=-1;
    }
    return ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57