Submission #822136

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
822136	2023-08-12T01:44:24 Z	Hanksburger	Game (APIO22_game)	C++17	2 / 100	9 ms	14464 KB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[300005], radj[300005];
int l[300005], r[300005];
void init(int n, int k)
{
    for (int i=0; i<k; i++)
        l[i]=i, r[i]=i;
    for (int i=k; i<n; i++)
        l[i]=-1, r[i]=k+1;
}
int recur(int u, int v)
{
    if (l[u]>=r[v])
        return 1;
    int midu=(l[u]+r[u])/2, midv=(l[v]+r[v])/2;
    if (l[u]>midv)
    {
        l[v]=midv+1;
        midv=(l[v]+r[v])/2;
        if (l[u]<=midv)
        {
            for (int w:adj[v])
                if (recur(v, w))
                    return 1;
            for (int w:radj[v])
                if (w!=u && recur(w, v))
                    return 1;
        }
    }
    if (r[v]<=midu)
    {
        r[u]=midu;
        midu=(l[u]+r[u])/2;
        if (r[v]>midu)
        {
            for (int w:adj[u])
                if (w!=v && recur(u, w))
                    return 1;
            for (int w:radj[u])
                if (recur(w, u))
                    return 1;
        }
    }
    return 0;
}
int add_teleporter(int u, int v)
{
    adj[u].push_back(v), radj[v].push_back(u);
    return recur(u, v);
}

Subtask #1

2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	14288 KB	Output is correct
2	Correct	8 ms	14288 KB	Output is correct
3	Correct	6 ms	14288 KB	Output is correct
4	Correct	8 ms	14288 KB	Output is correct
5	Correct	7 ms	14288 KB	Output is correct
6	Correct	9 ms	14324 KB	Output is correct
7	Correct	8 ms	14288 KB	Output is correct

Subtask #2

0.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	14288 KB	Output is correct
2	Correct	8 ms	14288 KB	Output is correct
3	Correct	6 ms	14288 KB	Output is correct
4	Correct	8 ms	14288 KB	Output is correct
5	Correct	7 ms	14288 KB	Output is correct
6	Correct	9 ms	14324 KB	Output is correct
7	Correct	8 ms	14288 KB	Output is correct
8	Correct	8 ms	14296 KB	Output is correct
9	Correct	8 ms	14304 KB	Output is correct
10	Correct	8 ms	14288 KB	Output is correct
11	Correct	9 ms	14416 KB	Output is correct
12	Correct	7 ms	14288 KB	Output is correct
13	Correct	7 ms	14400 KB	Output is correct
14	Incorrect	8 ms	14464 KB	Wrong Answer[1]
15	Halted	0 ms	0 KB	-

Subtask #3

0.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	14288 KB	Output is correct
2	Correct	8 ms	14288 KB	Output is correct
3	Correct	6 ms	14288 KB	Output is correct
4	Correct	8 ms	14288 KB	Output is correct
5	Correct	7 ms	14288 KB	Output is correct
6	Correct	9 ms	14324 KB	Output is correct
7	Correct	8 ms	14288 KB	Output is correct
8	Correct	8 ms	14296 KB	Output is correct
9	Correct	8 ms	14304 KB	Output is correct
10	Correct	8 ms	14288 KB	Output is correct
11	Correct	9 ms	14416 KB	Output is correct
12	Correct	7 ms	14288 KB	Output is correct
13	Correct	7 ms	14400 KB	Output is correct
14	Incorrect	8 ms	14464 KB	Wrong Answer[1]
15	Halted	0 ms	0 KB	-

Subtask #4

0.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	14288 KB	Output is correct
2	Correct	8 ms	14288 KB	Output is correct
3	Correct	6 ms	14288 KB	Output is correct
4	Correct	8 ms	14288 KB	Output is correct
5	Correct	7 ms	14288 KB	Output is correct
6	Correct	9 ms	14324 KB	Output is correct
7	Correct	8 ms	14288 KB	Output is correct
8	Correct	8 ms	14296 KB	Output is correct
9	Correct	8 ms	14304 KB	Output is correct
10	Correct	8 ms	14288 KB	Output is correct
11	Correct	9 ms	14416 KB	Output is correct
12	Correct	7 ms	14288 KB	Output is correct
13	Correct	7 ms	14400 KB	Output is correct
14	Incorrect	8 ms	14464 KB	Wrong Answer[1]
15	Halted	0 ms	0 KB	-

Subtask #5

0.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	14288 KB	Output is correct
2	Correct	8 ms	14288 KB	Output is correct
3	Correct	6 ms	14288 KB	Output is correct
4	Correct	8 ms	14288 KB	Output is correct
5	Correct	7 ms	14288 KB	Output is correct
6	Correct	9 ms	14324 KB	Output is correct
7	Correct	8 ms	14288 KB	Output is correct
8	Correct	8 ms	14296 KB	Output is correct
9	Correct	8 ms	14304 KB	Output is correct
10	Correct	8 ms	14288 KB	Output is correct
11	Correct	9 ms	14416 KB	Output is correct
12	Correct	7 ms	14288 KB	Output is correct
13	Correct	7 ms	14400 KB	Output is correct
14	Incorrect	8 ms	14464 KB	Wrong Answer[1]
15	Halted	0 ms	0 KB	-