oj.uz

Submission #642418

# Submission time Handle Problem Language Result Execution time Memory
642418 2022-09-19T11:54:38 Z berr Joker (BOI20_joker) C++17
0 / 100
 7 ms 13264 KB 
#include <bits/stdc++.h>
using namespace std;
int n, m, q, flag;
vector<array<int, 2>> adj[(int)3e5], check((int)3e5);
vector<int> val((int)3e5, (int)1e9), vis((int)(3e5), -1), de((int)(3e5), -1);
int cur=1;

void dfs(int p, int x, int y, int z, int par)
{
    de[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]]!=cur)  dfs(i[0], x, y, z+1, p);
        else if(vis[i[0]]==cur&&(z+de[i[0]]+1)%2==1) flag=1; 
    }
}

int bs(int pos)
{
 
    int s=pos;
    for(int i=18; i>=0; i--)
    {
        if(s+(1<<i)<=m) 
        {
            int tmp=(s+(1<<i));
            flag=0;

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

cur++;
            flag=0;
                    for(int i=1; i<=n; i++) if(vis[i]!=cur) 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]==1e9)
            val[l]=bs(l);
            if(val[l]<r) cout<<"NO\n";
            else cout<<"YES\n";
        }
    }
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 13264 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 13264 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 13264 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 13264 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 13264 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 13264 KB Output isn't correct
2 Halted 0 ms 0 KB -