답안 #648593

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
648593	2022-10-07T06:36:30 Z	mychecksedad	Joker (BOI20_joker)	C++17	14 / 100	207 ms	65228 KB

Joker

/* Author : Mychecksdead */
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define oset tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;


int n, m, q, l, r;
bool ok;
vector<pair<int, int>> g[N];
bitset<M> vis, pos;
void dfs(int v, int p, bool c){
    vis[v] = 1;
    pos[v] = c;
    for(auto k: g[v]){
        int u = k.first;
        if(l <= k.second && k.second <= r) continue;
        if(u != p){
            if(vis[u]){
                ok |= pos[v] == pos[u];
            }
            else
                dfs(u, v, !c);
        }
    }
}
void solve(){
    cin >> n >> m >> q;
    for(int i = 0; i < m; ++i){
        int u, v; cin >> u >> v;
        g[u].pb({v, i + 1});
        g[v].pb({u, i + 1});
    }
    if(n <= 2000 || q <= 1000){
        for(int i = 0; i < q; ++i){
            cin >> l >> r;
            vis = 0;
            ok = 0;
            for(int v = 1; v <= n; ++v) if(!ok && !vis[v]) dfs(v, v, 0);
            if(ok) cout << "YES\n";
            else cout << "NO\n";
        }
    }
    else{
        int lb = 1, rb = q, lim = q + 1;
        while(lb <= rb){
            int mid = (lb + rb) >> 1;
            l = 1, r = mid;
            vis = 0;
            ok = 0;
            for(int v = 1; v <= n; ++v) if(!ok && !vis[v]) dfs(v, v, 0);
            if(ok){
                lim = mid;
                lb = mid + 1;
            }else{
                rb = mid - 1;
            }
        }
        for(int i = 1; i <= q; ++i){
            cin >> l >> r;
            cout << (r <= lim ? "YES": "NO") << '\n';
        }
    }
}





int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
        cout << '\n';
    }
    return 0;
 
}

Compilation message

Joker.cpp: In function 'int main()':
Joker.cpp:83:16: warning: unused variable 'aa' [-Wunused-variable]
   83 |     int T = 1, aa;
      |                ^~

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	23764 KB	Output is correct
2	Correct	11 ms	23764 KB	Output is correct
3	Correct	11 ms	23748 KB	Output is correct
4	Correct	11 ms	23832 KB	Output is correct
5	Correct	12 ms	23764 KB	Output is correct
6	Correct	13 ms	23752 KB	Output is correct
7	Correct	12 ms	23764 KB	Output is correct
8	Correct	13 ms	23800 KB	Output is correct
9	Correct	12 ms	23764 KB	Output is correct
10	Correct	12 ms	23764 KB	Output is correct
11	Correct	13 ms	23764 KB	Output is correct
12	Correct	13 ms	23764 KB	Output is correct
13	Correct	13 ms	23744 KB	Output is correct
14	Correct	12 ms	23764 KB	Output is correct
15	Correct	13 ms	23764 KB	Output is correct
16	Correct	12 ms	23840 KB	Output is correct
17	Correct	13 ms	23784 KB	Output is correct
18	Correct	14 ms	23844 KB	Output is correct
19	Correct	12 ms	23844 KB	Output is correct
20	Correct	12 ms	23764 KB	Output is correct
21	Correct	12 ms	23840 KB	Output is correct
22	Correct	15 ms	23824 KB	Output is correct
23	Correct	12 ms	23764 KB	Output is correct
24	Correct	14 ms	23764 KB	Output is correct
25	Correct	14 ms	23856 KB	Output is correct
26	Correct	13 ms	23764 KB	Output is correct
27	Correct	14 ms	23764 KB	Output is correct
28	Correct	12 ms	23764 KB	Output is correct

Subtask #2
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	23764 KB	Output is correct
2	Correct	11 ms	23764 KB	Output is correct
3	Correct	11 ms	23748 KB	Output is correct
4	Correct	11 ms	23832 KB	Output is correct
5	Correct	12 ms	23764 KB	Output is correct
6	Correct	13 ms	23752 KB	Output is correct
7	Correct	12 ms	23764 KB	Output is correct
8	Correct	13 ms	23800 KB	Output is correct
9	Correct	12 ms	23764 KB	Output is correct
10	Correct	12 ms	23764 KB	Output is correct
11	Correct	13 ms	23764 KB	Output is correct
12	Correct	13 ms	23764 KB	Output is correct
13	Correct	13 ms	23744 KB	Output is correct
14	Correct	12 ms	23764 KB	Output is correct
15	Correct	13 ms	23764 KB	Output is correct
16	Correct	12 ms	23840 KB	Output is correct
17	Correct	13 ms	23784 KB	Output is correct
18	Correct	14 ms	23844 KB	Output is correct
19	Correct	12 ms	23844 KB	Output is correct
20	Correct	12 ms	23764 KB	Output is correct
21	Correct	12 ms	23840 KB	Output is correct
22	Correct	15 ms	23824 KB	Output is correct
23	Correct	12 ms	23764 KB	Output is correct
24	Correct	14 ms	23764 KB	Output is correct
25	Correct	14 ms	23856 KB	Output is correct
26	Correct	13 ms	23764 KB	Output is correct
27	Correct	14 ms	23764 KB	Output is correct
28	Correct	12 ms	23764 KB	Output is correct
29	Correct	80 ms	23860 KB	Output is correct
30	Correct	94 ms	23912 KB	Output is correct
31	Correct	104 ms	23952 KB	Output is correct
32	Correct	88 ms	23936 KB	Output is correct
33	Correct	71 ms	23916 KB	Output is correct
34	Correct	92 ms	23940 KB	Output is correct
35	Correct	112 ms	23892 KB	Output is correct
36	Correct	46 ms	23892 KB	Output is correct
37	Correct	87 ms	24064 KB	Output is correct
38	Correct	90 ms	23908 KB	Output is correct
39	Correct	87 ms	23948 KB	Output is correct
40	Correct	81 ms	23892 KB	Output is correct
41	Correct	83 ms	23948 KB	Output is correct
42	Correct	87 ms	23892 KB	Output is correct
43	Correct	81 ms	23924 KB	Output is correct
44	Correct	104 ms	23892 KB	Output is correct
45	Correct	114 ms	23832 KB	Output is correct
46	Correct	114 ms	23928 KB	Output is correct
47	Correct	83 ms	23920 KB	Output is correct
48	Correct	92 ms	24044 KB	Output is correct
49	Correct	92 ms	23892 KB	Output is correct
50	Correct	93 ms	23916 KB	Output is correct
51	Correct	77 ms	23924 KB	Output is correct
52	Correct	94 ms	23936 KB	Output is correct
53	Correct	105 ms	23932 KB	Output is correct
54	Correct	108 ms	23944 KB	Output is correct

Subtask #3
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	23764 KB	Output is correct
2	Correct	11 ms	23764 KB	Output is correct
3	Correct	207 ms	35904 KB	Output is correct
4	Runtime error	99 ms	65228 KB	Execution killed with signal 11
5	Halted	0 ms	0 KB	-

Subtask #4
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	23764 KB	Output is correct
2	Correct	11 ms	23764 KB	Output is correct
3	Correct	11 ms	23748 KB	Output is correct
4	Correct	11 ms	23832 KB	Output is correct
5	Correct	12 ms	23764 KB	Output is correct
6	Correct	13 ms	23752 KB	Output is correct
7	Correct	12 ms	23764 KB	Output is correct
8	Correct	13 ms	23800 KB	Output is correct
9	Correct	12 ms	23764 KB	Output is correct
10	Correct	12 ms	23764 KB	Output is correct
11	Correct	13 ms	23764 KB	Output is correct
12	Correct	13 ms	23764 KB	Output is correct
13	Correct	13 ms	23744 KB	Output is correct
14	Correct	12 ms	23764 KB	Output is correct
15	Correct	13 ms	23764 KB	Output is correct
16	Correct	12 ms	23840 KB	Output is correct
17	Correct	13 ms	23784 KB	Output is correct
18	Correct	14 ms	23844 KB	Output is correct
19	Correct	12 ms	23844 KB	Output is correct
20	Correct	12 ms	23764 KB	Output is correct
21	Correct	12 ms	23840 KB	Output is correct
22	Correct	15 ms	23824 KB	Output is correct
23	Correct	12 ms	23764 KB	Output is correct
24	Correct	14 ms	23764 KB	Output is correct
25	Correct	14 ms	23856 KB	Output is correct
26	Correct	13 ms	23764 KB	Output is correct
27	Correct	14 ms	23764 KB	Output is correct
28	Correct	12 ms	23764 KB	Output is correct
29	Correct	207 ms	35904 KB	Output is correct
30	Runtime error	99 ms	65228 KB	Execution killed with signal 11
31	Halted	0 ms	0 KB	-

Subtask #5
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	23764 KB	Output is correct
2	Correct	11 ms	23764 KB	Output is correct
3	Correct	11 ms	23748 KB	Output is correct
4	Correct	11 ms	23832 KB	Output is correct
5	Correct	12 ms	23764 KB	Output is correct
6	Correct	13 ms	23752 KB	Output is correct
7	Correct	12 ms	23764 KB	Output is correct
8	Correct	13 ms	23800 KB	Output is correct
9	Correct	12 ms	23764 KB	Output is correct
10	Correct	12 ms	23764 KB	Output is correct
11	Correct	13 ms	23764 KB	Output is correct
12	Correct	13 ms	23764 KB	Output is correct
13	Correct	13 ms	23744 KB	Output is correct
14	Correct	12 ms	23764 KB	Output is correct
15	Correct	13 ms	23764 KB	Output is correct
16	Correct	12 ms	23840 KB	Output is correct
17	Correct	13 ms	23784 KB	Output is correct
18	Correct	14 ms	23844 KB	Output is correct
19	Correct	12 ms	23844 KB	Output is correct
20	Correct	12 ms	23764 KB	Output is correct
21	Correct	12 ms	23840 KB	Output is correct
22	Correct	15 ms	23824 KB	Output is correct
23	Correct	12 ms	23764 KB	Output is correct
24	Correct	14 ms	23764 KB	Output is correct
25	Correct	14 ms	23856 KB	Output is correct
26	Correct	13 ms	23764 KB	Output is correct
27	Correct	14 ms	23764 KB	Output is correct
28	Correct	12 ms	23764 KB	Output is correct
29	Correct	80 ms	23860 KB	Output is correct
30	Correct	94 ms	23912 KB	Output is correct
31	Correct	104 ms	23952 KB	Output is correct
32	Correct	88 ms	23936 KB	Output is correct
33	Correct	71 ms	23916 KB	Output is correct
34	Correct	92 ms	23940 KB	Output is correct
35	Correct	112 ms	23892 KB	Output is correct
36	Correct	46 ms	23892 KB	Output is correct
37	Correct	87 ms	24064 KB	Output is correct
38	Correct	90 ms	23908 KB	Output is correct
39	Correct	87 ms	23948 KB	Output is correct
40	Correct	81 ms	23892 KB	Output is correct
41	Correct	83 ms	23948 KB	Output is correct
42	Correct	87 ms	23892 KB	Output is correct
43	Correct	81 ms	23924 KB	Output is correct
44	Correct	104 ms	23892 KB	Output is correct
45	Correct	114 ms	23832 KB	Output is correct
46	Correct	114 ms	23928 KB	Output is correct
47	Correct	83 ms	23920 KB	Output is correct
48	Correct	92 ms	24044 KB	Output is correct
49	Correct	92 ms	23892 KB	Output is correct
50	Correct	93 ms	23916 KB	Output is correct
51	Correct	77 ms	23924 KB	Output is correct
52	Correct	94 ms	23936 KB	Output is correct
53	Correct	105 ms	23932 KB	Output is correct
54	Correct	108 ms	23944 KB	Output is correct
55	Incorrect	139 ms	35820 KB	Output isn't correct
56	Halted	0 ms	0 KB	-

Subtask #6
0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	23764 KB	Output is correct
2	Correct	11 ms	23764 KB	Output is correct
3	Correct	11 ms	23748 KB	Output is correct
4	Correct	11 ms	23832 KB	Output is correct
5	Correct	12 ms	23764 KB	Output is correct
6	Correct	13 ms	23752 KB	Output is correct
7	Correct	12 ms	23764 KB	Output is correct
8	Correct	13 ms	23800 KB	Output is correct
9	Correct	12 ms	23764 KB	Output is correct
10	Correct	12 ms	23764 KB	Output is correct
11	Correct	13 ms	23764 KB	Output is correct
12	Correct	13 ms	23764 KB	Output is correct
13	Correct	13 ms	23744 KB	Output is correct
14	Correct	12 ms	23764 KB	Output is correct
15	Correct	13 ms	23764 KB	Output is correct
16	Correct	12 ms	23840 KB	Output is correct
17	Correct	13 ms	23784 KB	Output is correct
18	Correct	14 ms	23844 KB	Output is correct
19	Correct	12 ms	23844 KB	Output is correct
20	Correct	12 ms	23764 KB	Output is correct
21	Correct	12 ms	23840 KB	Output is correct
22	Correct	15 ms	23824 KB	Output is correct
23	Correct	12 ms	23764 KB	Output is correct
24	Correct	14 ms	23764 KB	Output is correct
25	Correct	14 ms	23856 KB	Output is correct
26	Correct	13 ms	23764 KB	Output is correct
27	Correct	14 ms	23764 KB	Output is correct
28	Correct	12 ms	23764 KB	Output is correct
29	Correct	80 ms	23860 KB	Output is correct
30	Correct	94 ms	23912 KB	Output is correct
31	Correct	104 ms	23952 KB	Output is correct
32	Correct	88 ms	23936 KB	Output is correct
33	Correct	71 ms	23916 KB	Output is correct
34	Correct	92 ms	23940 KB	Output is correct
35	Correct	112 ms	23892 KB	Output is correct
36	Correct	46 ms	23892 KB	Output is correct
37	Correct	87 ms	24064 KB	Output is correct
38	Correct	90 ms	23908 KB	Output is correct
39	Correct	87 ms	23948 KB	Output is correct
40	Correct	81 ms	23892 KB	Output is correct
41	Correct	83 ms	23948 KB	Output is correct
42	Correct	87 ms	23892 KB	Output is correct
43	Correct	81 ms	23924 KB	Output is correct
44	Correct	104 ms	23892 KB	Output is correct
45	Correct	114 ms	23832 KB	Output is correct
46	Correct	114 ms	23928 KB	Output is correct
47	Correct	83 ms	23920 KB	Output is correct
48	Correct	92 ms	24044 KB	Output is correct
49	Correct	92 ms	23892 KB	Output is correct
50	Correct	93 ms	23916 KB	Output is correct
51	Correct	77 ms	23924 KB	Output is correct
52	Correct	94 ms	23936 KB	Output is correct
53	Correct	105 ms	23932 KB	Output is correct
54	Correct	108 ms	23944 KB	Output is correct
55	Correct	207 ms	35904 KB	Output is correct
56	Runtime error	99 ms	65228 KB	Execution killed with signal 11
57	Halted	0 ms	0 KB	-

답안 #648593

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 8.0 / 8.0

Subtask #3 0 / 25.0

Subtask #4 0 / 10.0

Subtask #5 0 / 22.0

Subtask #6 0 / 29.0

Subtask #1
6.0 / 6.0

Subtask #2
8.0 / 8.0

Subtask #3
0 / 25.0

Subtask #4
0 / 10.0

Subtask #5
0 / 22.0

Subtask #6
0 / 29.0