Submission #914394

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
914394	2024-01-21T21:42:37 Z	Abito	Joker (BOI20_joker)	C++17	25 / 100	379 ms	20936 KB

Joker

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
#define int long long
#define ll long long
#define y1 YONE
#define free freeee
#define lcm llcm
/*
⠄⠄⠄⠄⢠⣿⣿⣿⣿⣿⢻⣿⣿⣿⣿⣿⣿⣿⣿⣯⢻⣿⣿⣿⣿⣆⠄⠄⠄
⠄⠄⣼⢀⣿⣿⣿⣿⣏⡏⠄⠹⣿⣿⣿⣿⣿⣿⣿⣿⣧⢻⣿⣿⣿⣿⡆⠄⠄
⠄⠄⡟⣼⣿⣿⣿⣿⣿⠄⠄⠄⠈⠻⣿⣿⣿⣿⣿⣿⣿⣇⢻⣿⣿⣿⣿⠄⠄
⠄⢰⠃⣿⣿⠿⣿⣿⣿⠄⠄⠄⠄⠄⠄⠙⠿⣿⣿⣿⣿⣿⠄⢿⣿⣿⣿⡄⠄
⠄⢸⢠⣿⣿⣧⡙⣿⣿⡆⠄⠄⠄⠄⠄⠄⠄⠈⠛⢿⣿⣿⡇⠸⣿⡿⣸⡇⠄
⠄⠈⡆⣿⣿⣿⣿⣦⡙⠳⠄⠄⠄⠄⠄⠄⢀⣠⣤⣀⣈⠙⠃⠄⠿⢇⣿⡇⠄
⠄⠄⡇⢿⣿⣿⣿⣿⡇⠄⠄⠄⠄⠄⣠⣶⣿⣿⣿⣿⣿⣿⣷⣆⡀⣼⣿⡇⠄
⠄⠄⢹⡘⣿⣿⣿⢿⣷⡀⠄⢀⣴⣾⣟⠉⠉⠉⠉⣽⣿⣿⣿⣿⠇⢹⣿⠃⠄
⠄⠄⠄⢷⡘⢿⣿⣎⢻⣷⠰⣿⣿⣿⣿⣦⣀⣀⣴⣿⣿⣿⠟⢫⡾⢸⡟⠄.
⠄⠄⠄⠄⠻⣦⡙⠿⣧⠙⢷⠙⠻⠿⢿⡿⠿⠿⠛⠋⠉⠄⠂⠘⠁⠞⠄⠄⠄
⠄⠄⠄⠄⠄⠈⠙⠑⣠⣤⣴⡖⠄⠿⣋⣉⣉⡁⠄⢾⣦⠄⠄⠄⠄⠄⠄⠄⠄
*/
typedef unsigned long long ull;
using namespace std;
const int N=2e5+5;
int n,m,q,tin[N],t;
vector<pair<int,int>> adj[N];
bool vis[N],cyc;
void dfs(int x,int mid){
    vis[x]=1;
    tin[x]=++t;
    for (auto u:adj[x]){
        if (u.S<=mid) continue;
        if (vis[u.F]) cyc|=((tin[x]-tin[u.F]+1)&1);
        else dfs(u.F,mid);
    }t--;
    return;
}
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n>>m>>q;
    for (int i=1;i<=m;i++){
        int x,y;cin>>x>>y;
        adj[x].pb({y,i});
        adj[y].pb({x,i});
    }
    int l=1,r=m,mid,ans=0;
    while (l<=r){
        mid=(l+r)/2;
        memset(vis,0,sizeof(vis));cyc=0;
        for (int i=1;i<=n;i++) if (!vis[i]) dfs(i,mid);
        if (cyc) ans=mid,l=mid+1;
        else r=mid-1;
    }
    while (q--){
        cin>>l>>r;
        if (r<=ans) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

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

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	6744 KB	Output is correct
2	Correct	3 ms	6748 KB	Output is correct
3	Correct	222 ms	19536 KB	Output is correct
4	Correct	295 ms	19644 KB	Output is correct
5	Correct	223 ms	18820 KB	Output is correct
6	Correct	265 ms	20436 KB	Output is correct
7	Correct	214 ms	20564 KB	Output is correct
8	Correct	259 ms	20560 KB	Output is correct
9	Correct	270 ms	20936 KB	Output is correct
10	Correct	379 ms	19536 KB	Output is correct
11	Correct	200 ms	19528 KB	Output is correct
12	Correct	283 ms	18368 KB	Output is correct
13	Correct	125 ms	18772 KB	Output is correct
14	Correct	190 ms	20180 KB	Output is correct
15	Correct	351 ms	20372 KB	Output is correct
16	Correct	363 ms	19280 KB	Output is correct