답안 #821234

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
821234	2023-08-11T08:16:00 Z	Hanksburger	게임 (APIO22_game)	C++17	30 / 100	4000 ms	12364 KB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int tin[300005], mn[300005], ins[300005], scc[300005], n, k, t;
vector<int> adj[300005];
stack<int> s;
void init(int nn, int kk)
{
    n=nn;
    k=kk;
    for (int i=0; i<=k-2; i++)
        adj[i].push_back(i+1);
}
void dfs(int u)
{
    tin[u]=mn[u]=(++t);
    ins[u]=1;
    s.push(u);
    for (int v:adj[u])
    {
        if (!tin[v])
        {
            dfs(v);
            mn[u]=min(mn[u], mn[v]);
        }
        else if (ins[v])
            mn[u]=min(mn[u], tin[v]);
    }
    if (tin[u]==mn[u])
    {
        vector<int> vec;
        while (s.top()!=u)
        {
            vec.push_back(s.top());
            ins[s.top()]=0;
            s.pop();
        }
        vec.push_back(s.top());
        ins[s.top()]=0;
        s.pop();
        for (int i=0; i<vec.size(); i++)
            scc[vec[i]]=vec.size();
    }
}
int add_teleporter(int u, int v)
{
    if (u==v)
        return (u<k);
    adj[u].push_back(v);
    for (int i=0; i<n; i++)
        tin[i]=mn[i]=ins[i]=scc[i]=0;
    t=0;
    dfs(0);
    for (int i=0; i<k; i++)
        if (scc[i]>1)
            return 1;
    return 0;
}

Compilation message

game.cpp: In function 'void dfs(int)':
game.cpp:41:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for (int i=0; i<vec.size(); i++)
      |                       ~^~~~~~~~~~~

Subtask #1

2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	7248 KB	Output is correct
2	Correct	3 ms	7248 KB	Output is correct
3	Correct	4 ms	7376 KB	Output is correct
4	Correct	3 ms	7248 KB	Output is correct
5	Correct	9 ms	7376 KB	Output is correct
6	Correct	4 ms	7376 KB	Output is correct
7	Correct	4 ms	7376 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	7248 KB	Output is correct
2	Correct	3 ms	7248 KB	Output is correct
3	Correct	4 ms	7376 KB	Output is correct
4	Correct	3 ms	7248 KB	Output is correct
5	Correct	9 ms	7376 KB	Output is correct
6	Correct	4 ms	7376 KB	Output is correct
7	Correct	4 ms	7376 KB	Output is correct
8	Correct	3 ms	7248 KB	Output is correct
9	Correct	3 ms	7320 KB	Output is correct
10	Correct	4 ms	7248 KB	Output is correct
11	Correct	3 ms	7288 KB	Output is correct
12	Correct	3 ms	7300 KB	Output is correct
13	Correct	3 ms	7248 KB	Output is correct
14	Correct	3 ms	7376 KB	Output is correct
15	Correct	4 ms	7376 KB	Output is correct
16	Correct	4 ms	7376 KB	Output is correct
17	Correct	4 ms	7376 KB	Output is correct
18	Correct	3 ms	7248 KB	Output is correct
19	Correct	4 ms	7248 KB	Output is correct

Subtask #3

18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	7248 KB	Output is correct
2	Correct	3 ms	7248 KB	Output is correct
3	Correct	4 ms	7376 KB	Output is correct
4	Correct	3 ms	7248 KB	Output is correct
5	Correct	9 ms	7376 KB	Output is correct
6	Correct	4 ms	7376 KB	Output is correct
7	Correct	4 ms	7376 KB	Output is correct
8	Correct	3 ms	7248 KB	Output is correct
9	Correct	3 ms	7320 KB	Output is correct
10	Correct	4 ms	7248 KB	Output is correct
11	Correct	3 ms	7288 KB	Output is correct
12	Correct	3 ms	7300 KB	Output is correct
13	Correct	3 ms	7248 KB	Output is correct
14	Correct	3 ms	7376 KB	Output is correct
15	Correct	4 ms	7376 KB	Output is correct
16	Correct	4 ms	7376 KB	Output is correct
17	Correct	4 ms	7376 KB	Output is correct
18	Correct	3 ms	7248 KB	Output is correct
19	Correct	4 ms	7248 KB	Output is correct
20	Correct	4 ms	7380 KB	Output is correct
21	Correct	3 ms	7376 KB	Output is correct
22	Correct	6 ms	7456 KB	Output is correct
23	Correct	4 ms	7376 KB	Output is correct
24	Correct	25 ms	7488 KB	Output is correct
25	Correct	88 ms	7456 KB	Output is correct
26	Correct	110 ms	7628 KB	Output is correct
27	Correct	134 ms	7464 KB	Output is correct
28	Correct	45 ms	7464 KB	Output is correct
29	Correct	93 ms	7452 KB	Output is correct

Subtask #4

0.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	7248 KB	Output is correct
2	Correct	3 ms	7248 KB	Output is correct
3	Correct	4 ms	7376 KB	Output is correct
4	Correct	3 ms	7248 KB	Output is correct
5	Correct	9 ms	7376 KB	Output is correct
6	Correct	4 ms	7376 KB	Output is correct
7	Correct	4 ms	7376 KB	Output is correct
8	Correct	3 ms	7248 KB	Output is correct
9	Correct	3 ms	7320 KB	Output is correct
10	Correct	4 ms	7248 KB	Output is correct
11	Correct	3 ms	7288 KB	Output is correct
12	Correct	3 ms	7300 KB	Output is correct
13	Correct	3 ms	7248 KB	Output is correct
14	Correct	3 ms	7376 KB	Output is correct
15	Correct	4 ms	7376 KB	Output is correct
16	Correct	4 ms	7376 KB	Output is correct
17	Correct	4 ms	7376 KB	Output is correct
18	Correct	3 ms	7248 KB	Output is correct
19	Correct	4 ms	7248 KB	Output is correct
20	Correct	4 ms	7380 KB	Output is correct
21	Correct	3 ms	7376 KB	Output is correct
22	Correct	6 ms	7456 KB	Output is correct
23	Correct	4 ms	7376 KB	Output is correct
24	Correct	25 ms	7488 KB	Output is correct
25	Correct	88 ms	7456 KB	Output is correct
26	Correct	110 ms	7628 KB	Output is correct
27	Correct	134 ms	7464 KB	Output is correct
28	Correct	45 ms	7464 KB	Output is correct
29	Correct	93 ms	7452 KB	Output is correct
30	Correct	614 ms	8320 KB	Output is correct
31	Correct	334 ms	8148 KB	Output is correct
32	Correct	318 ms	10844 KB	Output is correct
33	Correct	232 ms	8652 KB	Output is correct
34	Correct	2760 ms	12364 KB	Output is correct
35	Execution timed out	4027 ms	8560 KB	Time limit exceeded
36	Halted	0 ms	0 KB	-

Subtask #5

0.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	7248 KB	Output is correct
2	Correct	3 ms	7248 KB	Output is correct
3	Correct	4 ms	7376 KB	Output is correct
4	Correct	3 ms	7248 KB	Output is correct
5	Correct	9 ms	7376 KB	Output is correct
6	Correct	4 ms	7376 KB	Output is correct
7	Correct	4 ms	7376 KB	Output is correct
8	Correct	3 ms	7248 KB	Output is correct
9	Correct	3 ms	7320 KB	Output is correct
10	Correct	4 ms	7248 KB	Output is correct
11	Correct	3 ms	7288 KB	Output is correct
12	Correct	3 ms	7300 KB	Output is correct
13	Correct	3 ms	7248 KB	Output is correct
14	Correct	3 ms	7376 KB	Output is correct
15	Correct	4 ms	7376 KB	Output is correct
16	Correct	4 ms	7376 KB	Output is correct
17	Correct	4 ms	7376 KB	Output is correct
18	Correct	3 ms	7248 KB	Output is correct
19	Correct	4 ms	7248 KB	Output is correct
20	Correct	4 ms	7380 KB	Output is correct
21	Correct	3 ms	7376 KB	Output is correct
22	Correct	6 ms	7456 KB	Output is correct
23	Correct	4 ms	7376 KB	Output is correct
24	Correct	25 ms	7488 KB	Output is correct
25	Correct	88 ms	7456 KB	Output is correct
26	Correct	110 ms	7628 KB	Output is correct
27	Correct	134 ms	7464 KB	Output is correct
28	Correct	45 ms	7464 KB	Output is correct
29	Correct	93 ms	7452 KB	Output is correct
30	Correct	614 ms	8320 KB	Output is correct
31	Correct	334 ms	8148 KB	Output is correct
32	Correct	318 ms	10844 KB	Output is correct
33	Correct	232 ms	8652 KB	Output is correct
34	Correct	2760 ms	12364 KB	Output is correct
35	Execution timed out	4027 ms	8560 KB	Time limit exceeded
36	Halted	0 ms	0 KB	-