Submission #925739

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
925739	2024-02-12T08:02:49 Z	vjudge1	Joker (BOI20_joker)	C++17	6 / 100	2000 ms	12088 KB

Joker

//Bismillahir-Rahmanir-Rahim

#include <bits/stdc++.h>
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,popcnt,avx,avx2")

#define pb push_back
#define pii pair <int, int>
#define pll pair <long long, long long>
#define pld pair <long double, long double>
#define ll long long
#define ld long double
#define x first
#define y second
#define all(v) v.begin(),v.end()
#define sz(s) (int)s.size()
#define skip continue
#define bpop(x) (ll)__builtin_popcountll(x)

using namespace std;

const int N = 2e5 + 7;
const int M = 1e3 + 7;
const int maxA = 2e6 + 7;
const int inf = 1e9 + 7;
const ll INF = 2e18 + 7;
const int MOD = 1e9 + 7;
const ld eps = 1e-9;

pii dir[] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define int long long

pii E[N];
vector <int> g[N];
int n, m, q, dist[N];
bool bfs(int st) {
    for (int i = 1;i <= n;i++)dist[i] = -1;
    queue <int> q;
    q.push(st), dist[st] = 0;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (auto to : g[v]) {
            if (dist[to] == -1)dist[to] = dist[v] + 1, q.push(to);
            else if ((dist[v] + dist[to]) % 2 == 0) {
                //cout << v << ':' << dist[v] << ' ' << to << ':' << dist[to] << '\n';
                return 1;
            }
        }
    }
    return 0;
}
void subtask12() {
    while (q--) {
        int l, r;
        cin >> l >> r;
        for (int i = 1;i <= n;i++)g[i].clear(), dist[i] = -1;
        for (int i = 1;i <= m;i++) {
            if (l <= i && i <= r)skip;
            g[E[i].x].pb(E[i].y), g[E[i].y].pb(E[i].x);
            //cout << E[i].x << ' ' << E[i].y << '\n';
        }
        bool ans = 0;
        for (int i = 1;i <= n;i++) {
            if (dist[i] == -1)ans |= bfs(i);
        }
        cout << (ans ? "YES" : "NO") << '\n';
    }
}
void solve() {
    cin >> n >> m >> q;
    for (int i = 1;i <= m;i++) {
        int x, y;
        cin >> x >> y;
        E[i] = {x, y};
    }
    if (n <= 2000 && m <= 2000 && q <= 2000)subtask12();
}
signed main() {
    //srand(time(NULL));
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    //freopen("tests.in", "r", stdin);
    //freopen("milkorder.out", "w", stdout);
    int test = 1;
    //cin >> test;
    for (int t = 1;t <= test;t++) {
        //cout << "Case " << t << ": ";
        solve();
    }
    return 0;
}

Subtask #1
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	6492 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	2 ms	6492 KB	Output is correct
4	Correct	1 ms	6488 KB	Output is correct
5	Correct	1 ms	6492 KB	Output is correct
6	Correct	1 ms	6492 KB	Output is correct
7	Correct	5 ms	6492 KB	Output is correct
8	Correct	11 ms	6492 KB	Output is correct
9	Correct	9 ms	6488 KB	Output is correct
10	Correct	6 ms	6492 KB	Output is correct
11	Correct	11 ms	6620 KB	Output is correct
12	Correct	12 ms	6488 KB	Output is correct
13	Correct	3 ms	6492 KB	Output is correct
14	Correct	10 ms	6492 KB	Output is correct
15	Correct	9 ms	6492 KB	Output is correct
16	Correct	9 ms	6492 KB	Output is correct
17	Correct	5 ms	6492 KB	Output is correct
18	Correct	5 ms	6492 KB	Output is correct
19	Correct	5 ms	6488 KB	Output is correct
20	Correct	2 ms	6492 KB	Output is correct
21	Correct	4 ms	6492 KB	Output is correct
22	Correct	7 ms	6492 KB	Output is correct
23	Correct	4 ms	6628 KB	Output is correct
24	Correct	6 ms	6620 KB	Output is correct
25	Correct	10 ms	6492 KB	Output is correct
26	Correct	3 ms	6488 KB	Output is correct
27	Correct	6 ms	6488 KB	Output is correct
28	Correct	9 ms	6492 KB	Output is correct

Subtask #2
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	6492 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	2 ms	6492 KB	Output is correct
4	Correct	1 ms	6488 KB	Output is correct
5	Correct	1 ms	6492 KB	Output is correct
6	Correct	1 ms	6492 KB	Output is correct
7	Correct	5 ms	6492 KB	Output is correct
8	Correct	11 ms	6492 KB	Output is correct
9	Correct	9 ms	6488 KB	Output is correct
10	Correct	6 ms	6492 KB	Output is correct
11	Correct	11 ms	6620 KB	Output is correct
12	Correct	12 ms	6488 KB	Output is correct
13	Correct	3 ms	6492 KB	Output is correct
14	Correct	10 ms	6492 KB	Output is correct
15	Correct	9 ms	6492 KB	Output is correct
16	Correct	9 ms	6492 KB	Output is correct
17	Correct	5 ms	6492 KB	Output is correct
18	Correct	5 ms	6492 KB	Output is correct
19	Correct	5 ms	6488 KB	Output is correct
20	Correct	2 ms	6492 KB	Output is correct
21	Correct	4 ms	6492 KB	Output is correct
22	Correct	7 ms	6492 KB	Output is correct
23	Correct	4 ms	6628 KB	Output is correct
24	Correct	6 ms	6620 KB	Output is correct
25	Correct	10 ms	6492 KB	Output is correct
26	Correct	3 ms	6488 KB	Output is correct
27	Correct	6 ms	6488 KB	Output is correct
28	Correct	9 ms	6492 KB	Output is correct
29	Correct	1219 ms	6680 KB	Output is correct
30	Execution timed out	2053 ms	6716 KB	Time limit exceeded
31	Halted	0 ms	0 KB	-

Subtask #3
0 / 25.0

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

Subtask #4
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	6492 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	2 ms	6492 KB	Output is correct
4	Correct	1 ms	6488 KB	Output is correct
5	Correct	1 ms	6492 KB	Output is correct
6	Correct	1 ms	6492 KB	Output is correct
7	Correct	5 ms	6492 KB	Output is correct
8	Correct	11 ms	6492 KB	Output is correct
9	Correct	9 ms	6488 KB	Output is correct
10	Correct	6 ms	6492 KB	Output is correct
11	Correct	11 ms	6620 KB	Output is correct
12	Correct	12 ms	6488 KB	Output is correct
13	Correct	3 ms	6492 KB	Output is correct
14	Correct	10 ms	6492 KB	Output is correct
15	Correct	9 ms	6492 KB	Output is correct
16	Correct	9 ms	6492 KB	Output is correct
17	Correct	5 ms	6492 KB	Output is correct
18	Correct	5 ms	6492 KB	Output is correct
19	Correct	5 ms	6488 KB	Output is correct
20	Correct	2 ms	6492 KB	Output is correct
21	Correct	4 ms	6492 KB	Output is correct
22	Correct	7 ms	6492 KB	Output is correct
23	Correct	4 ms	6628 KB	Output is correct
24	Correct	6 ms	6620 KB	Output is correct
25	Correct	10 ms	6492 KB	Output is correct
26	Correct	3 ms	6488 KB	Output is correct
27	Correct	6 ms	6488 KB	Output is correct
28	Correct	9 ms	6492 KB	Output is correct
29	Incorrect	29 ms	12088 KB	Output isn't correct
30	Halted	0 ms	0 KB	-

Subtask #5
0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	6492 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	2 ms	6492 KB	Output is correct
4	Correct	1 ms	6488 KB	Output is correct
5	Correct	1 ms	6492 KB	Output is correct
6	Correct	1 ms	6492 KB	Output is correct
7	Correct	5 ms	6492 KB	Output is correct
8	Correct	11 ms	6492 KB	Output is correct
9	Correct	9 ms	6488 KB	Output is correct
10	Correct	6 ms	6492 KB	Output is correct
11	Correct	11 ms	6620 KB	Output is correct
12	Correct	12 ms	6488 KB	Output is correct
13	Correct	3 ms	6492 KB	Output is correct
14	Correct	10 ms	6492 KB	Output is correct
15	Correct	9 ms	6492 KB	Output is correct
16	Correct	9 ms	6492 KB	Output is correct
17	Correct	5 ms	6492 KB	Output is correct
18	Correct	5 ms	6492 KB	Output is correct
19	Correct	5 ms	6488 KB	Output is correct
20	Correct	2 ms	6492 KB	Output is correct
21	Correct	4 ms	6492 KB	Output is correct
22	Correct	7 ms	6492 KB	Output is correct
23	Correct	4 ms	6628 KB	Output is correct
24	Correct	6 ms	6620 KB	Output is correct
25	Correct	10 ms	6492 KB	Output is correct
26	Correct	3 ms	6488 KB	Output is correct
27	Correct	6 ms	6488 KB	Output is correct
28	Correct	9 ms	6492 KB	Output is correct
29	Correct	1219 ms	6680 KB	Output is correct
30	Execution timed out	2053 ms	6716 KB	Time limit exceeded
31	Halted	0 ms	0 KB	-

Subtask #6
0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	6492 KB	Output is correct
2	Correct	1 ms	6492 KB	Output is correct
3	Correct	2 ms	6492 KB	Output is correct
4	Correct	1 ms	6488 KB	Output is correct
5	Correct	1 ms	6492 KB	Output is correct
6	Correct	1 ms	6492 KB	Output is correct
7	Correct	5 ms	6492 KB	Output is correct
8	Correct	11 ms	6492 KB	Output is correct
9	Correct	9 ms	6488 KB	Output is correct
10	Correct	6 ms	6492 KB	Output is correct
11	Correct	11 ms	6620 KB	Output is correct
12	Correct	12 ms	6488 KB	Output is correct
13	Correct	3 ms	6492 KB	Output is correct
14	Correct	10 ms	6492 KB	Output is correct
15	Correct	9 ms	6492 KB	Output is correct
16	Correct	9 ms	6492 KB	Output is correct
17	Correct	5 ms	6492 KB	Output is correct
18	Correct	5 ms	6492 KB	Output is correct
19	Correct	5 ms	6488 KB	Output is correct
20	Correct	2 ms	6492 KB	Output is correct
21	Correct	4 ms	6492 KB	Output is correct
22	Correct	7 ms	6492 KB	Output is correct
23	Correct	4 ms	6628 KB	Output is correct
24	Correct	6 ms	6620 KB	Output is correct
25	Correct	10 ms	6492 KB	Output is correct
26	Correct	3 ms	6488 KB	Output is correct
27	Correct	6 ms	6488 KB	Output is correct
28	Correct	9 ms	6492 KB	Output is correct
29	Correct	1219 ms	6680 KB	Output is correct
30	Execution timed out	2053 ms	6716 KB	Time limit exceeded
31	Halted	0 ms	0 KB	-

Submission #925739

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 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
0 / 8.0

Subtask #3
0 / 25.0

Subtask #4
0 / 10.0

Subtask #5
0 / 22.0

Subtask #6
0 / 29.0