oj.uz

Submission #642411

# Submission time Handle Problem Language Result Execution time Memory
642411 2022-09-19T11:36:20 Z berr Joker (BOI20_joker) C++17
0 / 100
 2000 ms 33244 KB 
#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=20; 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});   
    }


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

        while(q--)
        {
            int l, r; cin>>l>>r;
            if(r>val[l]) cout<<"NO\n";
            else cout<<"YES\n";
        }
    }
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 8 ms 16724 KB Output is correct
3 Incorrect 8 ms 16708 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 8 ms 16724 KB Output is correct
3 Incorrect 8 ms 16708 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 8 ms 16724 KB Output is correct
3 Execution timed out 2037 ms 33244 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 8 ms 16724 KB Output is correct
3 Incorrect 8 ms 16708 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 8 ms 16724 KB Output is correct
3 Incorrect 8 ms 16708 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 8 ms 16724 KB Output is correct
3 Incorrect 8 ms 16708 KB Output isn't correct
4 Halted 0 ms 0 KB -