Submission #642415

#	Time	Username	Problem	Language	Result	Execution time	Memory
642415		berr	Joker (BOI20_joker)	C++17	14 / 100	2090 ms	31780 KiB

Joker

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m, q, flag;
vector<array<int, 2>> adj[(int)3e5], check((int)3e5);
vector<int> val((int)3e5, 1e18), vis((int)(3e5), -1);


void dfs(int p, int x, int y, int z, int par)
{
    vis[p]=z%2;
    if(y<x) swap(x, y);
    for(auto i: adj[p])
    {
        if(i[1]>=x&&i[1]<=y) continue;
        if(i[0]==par) continue;
        if(vis[i[0]]==-1)  dfs(i[0], x, y, z+1, p);
        else if(vis[i[0]]!=-1&&(z+vis[i[0]]+1)%2==1) flag=1; 
    }
}

int bs(int pos)
{
 
    int s=pos;
    for(int i=14; i>=0; i--)
    {
        if(s+(1<<i)<=m) 
        {
            int tmp=(s+(1<<i));
            for(int i=1; i<=n; i++) vis[i]=-1;
            flag=0;

            for(int i=1; i<=n; i++) if(vis[i]==-1) dfs(i, pos, tmp, 0, i);
            if(flag==1) s=tmp;

        }
    }

                for(int i=1; i<=n; i++) vis[i]=-1;
            flag=0;
                    for(int i=1; i<=n; i++) if(vis[i]==-1) dfs(i, pos, s, 0, i);
                        if(flag==0) s--;
    return s;
}

int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    
     cin>>n>>m>>q;

    for(int i=1; i<=m; i++)
    {
        int x, y; cin>>x>>y;
        adj[x].push_back({y, i});
        adj[y].push_back({x, i});   
    }

    set<int> s;
    if(n<=2000&&m<=2000&&q<=2000)
    {
        while(q--)
        {
            int l, r; cin>>l>>r;
            if(val[l]==1e18)
            val[l]=bs(l);
            if(val[l]<r) cout<<"NO\n";
            else cout<<"YES\n";
        }
    }
    else
    {
   
        while(q--)
        {
            int l, r; cin>>l>>r;
            if(val[l]==1e18)
            val[l]=bs(l);
            if(val[l]<r) cout<<"NO\n";
            else cout<<"YES\n";
        }
    }
}
    

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 0 / 25
• Subtask 4: 0 / 10
• Subtask 5: 0 / 22
• Subtask 6: 0 / 29