Submission #1178734

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178734		prideliqueee	Drivers (BOI24_drivers)	C++20	100 / 100	223 ms	19092 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
int p[200010];
struct edge
{
    int u,v,w;
    bool operator < (const edge &o) const
    {
        return w<o.w;
    }
};
struct st
{
    int x,y,t,in;
    bool operator < (const st&o) const
    {
        return t<o.t;
    }
};
int root(int u)
{
    if(p[u]==u)
    return u;
    return p[u]=root(p[u]);
}
signed main()
{
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
    p[i]=i;
    vector<edge> e;
    for(int i=0;i<m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        e.push_back({u,v,w});
    }
    sort(e.begin(),e.end());
    bool b[q];
    memset(b,0,sizeof b);
    vector<st> v;
    for(int i=0;i<q;i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
        v.push_back({x,y,w,i});
    }
    sort(v.begin(),v.end());
    int j=0;
    for(int i=0;i<q;i++)
    {
        int x=v[i].x,y=v[i].y,t=v[i].t,in=v[i].in;
        while(j<m)
        {
            int u=e[j].u,v=e[j].v,w=e[j].w;
            if(w<=t)
            {
                if(root(u)!=root(v))
                {
                    p[root(u)]=root(v);
                }
                j++;
            }
            else
            break;
        }
        if(root(x)==root(y))
        b[in]=1;
        //cout<<x<<" "<<y<<" "<<b[in]<<endl;
    }
    for(int i=0;i<q;i++)
    {
        if(b[i])
        cout<<"TAIP\n";
        else
        cout<<"NE\n";
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 23 / 23
• Subtask 5: 45 / 45