답안 #983515

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
983515	2024-05-15T15:26:46 Z	Alkaser_ID	게임 (APIO22_game)	C++17	12 / 100	41 ms	98136 KB

game

#include "game.h"
using namespace std;
#include <bits/stdc++.h>
const int sz = 1e6 + 5;

int res = 0,K=0;
set<int> scc[sz], rv[sz];
int c[sz]; bool b[sz];
void init(int n, int k) {
    K = k;
    for(int i=0;i<k;++i){
        b[i] = true;
        c[i] = i;
        if(i < k-1) {
            scc[i].insert(i+1);
        }
    }
    for(int i=k;i<n;++i) c[i] = i;
}

bool vis[sz]; set<int> s; int sp = 0;
vector<int> cv;
inline void cycle() {
    int C = *s.begin();
    set<int>::iterator it = s.begin();
    for(++it;it!=s.end();++it){
        for(set<int>::iterator j = scc[*it].begin();j != scc[*it].end();++j){
            scc[C].insert(*j);
            rv[*j].insert(C);
        }
        c[*it] = C;
        for(set<int>::iterator jt = rv[*it].begin();jt != rv[*it].end();++jt){
            scc[*jt].erase(*it);
            scc[*jt].insert(C);
        }
    }
    b[C] = (sp > 0);
    if(b[C]) res = 1;
}
inline void dfs(int i, int rt){
    s.insert(i); if(i <K) ++sp;
    vis[i] = true;
    cv.push_back(i);
    for(set<int>::iterator j=scc[i].begin();j!=scc[i].end();++j){
        if(*j == rt && !s.empty()) {
            cycle(); s.clear();
            return;
        }
        if(s.empty()) return;
        if(!vis[*j]) dfs(*j,rt);
    }
    if(s.empty()) return;
    s.erase(i); if(i < K) --sp;
}

int add_teleporter(int u, int v) {
    if(u == v) res = 1;
    if(c[u] == c[v] || res == 1) return res;
    scc[c[u]].insert(c[v]);
    rv[c[v]].insert(c[u]);
    dfs(c[u],c[u]);
    for(int j=0;j<cv.size();++j) {
        vis[cv[j]] = false;
    }
    cv.clear();
    return res;
}

/*
6 5 3
3 4
5 0
4 5
5 3
1 4

4 1 2
1 1

4 3 2
1 3
2 0
3 2

*/

Compilation message

game.cpp: In function 'int add_teleporter(int, int)':
game.cpp:62:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int j=0;j<cv.size();++j) {
      |                 ~^~~~~~~~~~

Subtask #1
2.0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	97924 KB	Output is correct
2	Correct	19 ms	97880 KB	Output is correct
3	Correct	22 ms	97880 KB	Output is correct
4	Correct	21 ms	97880 KB	Output is correct
5	Correct	21 ms	97880 KB	Output is correct
6	Correct	23 ms	97880 KB	Output is correct
7	Correct	22 ms	97880 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	97924 KB	Output is correct
2	Correct	19 ms	97880 KB	Output is correct
3	Correct	22 ms	97880 KB	Output is correct
4	Correct	21 ms	97880 KB	Output is correct
5	Correct	21 ms	97880 KB	Output is correct
6	Correct	23 ms	97880 KB	Output is correct
7	Correct	22 ms	97880 KB	Output is correct
8	Correct	21 ms	97936 KB	Output is correct
9	Correct	21 ms	98136 KB	Output is correct
10	Correct	22 ms	97984 KB	Output is correct
11	Correct	20 ms	97872 KB	Output is correct
12	Correct	19 ms	97880 KB	Output is correct
13	Correct	20 ms	97880 KB	Output is correct
14	Correct	22 ms	97932 KB	Output is correct
15	Correct	24 ms	98136 KB	Output is correct
16	Correct	21 ms	97936 KB	Output is correct
17	Correct	22 ms	97880 KB	Output is correct
18	Correct	21 ms	97916 KB	Output is correct
19	Correct	21 ms	97880 KB	Output is correct

Subtask #3
0.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	97924 KB	Output is correct
2	Correct	19 ms	97880 KB	Output is correct
3	Correct	22 ms	97880 KB	Output is correct
4	Correct	21 ms	97880 KB	Output is correct
5	Correct	21 ms	97880 KB	Output is correct
6	Correct	23 ms	97880 KB	Output is correct
7	Correct	22 ms	97880 KB	Output is correct
8	Correct	21 ms	97936 KB	Output is correct
9	Correct	21 ms	98136 KB	Output is correct
10	Correct	22 ms	97984 KB	Output is correct
11	Correct	20 ms	97872 KB	Output is correct
12	Correct	19 ms	97880 KB	Output is correct
13	Correct	20 ms	97880 KB	Output is correct
14	Correct	22 ms	97932 KB	Output is correct
15	Correct	24 ms	98136 KB	Output is correct
16	Correct	21 ms	97936 KB	Output is correct
17	Correct	22 ms	97880 KB	Output is correct
18	Correct	21 ms	97916 KB	Output is correct
19	Correct	21 ms	97880 KB	Output is correct
20	Correct	24 ms	97880 KB	Output is correct
21	Correct	22 ms	97880 KB	Output is correct
22	Correct	21 ms	98136 KB	Output is correct
23	Incorrect	20 ms	97880 KB	Wrong Answer[1]
24	Halted	0 ms	0 KB	-

Subtask #4
0.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	97924 KB	Output is correct
2	Correct	19 ms	97880 KB	Output is correct
3	Correct	22 ms	97880 KB	Output is correct
4	Correct	21 ms	97880 KB	Output is correct
5	Correct	21 ms	97880 KB	Output is correct
6	Correct	23 ms	97880 KB	Output is correct
7	Correct	22 ms	97880 KB	Output is correct
8	Correct	21 ms	97936 KB	Output is correct
9	Correct	21 ms	98136 KB	Output is correct
10	Correct	22 ms	97984 KB	Output is correct
11	Correct	20 ms	97872 KB	Output is correct
12	Correct	19 ms	97880 KB	Output is correct
13	Correct	20 ms	97880 KB	Output is correct
14	Correct	22 ms	97932 KB	Output is correct
15	Correct	24 ms	98136 KB	Output is correct
16	Correct	21 ms	97936 KB	Output is correct
17	Correct	22 ms	97880 KB	Output is correct
18	Correct	21 ms	97916 KB	Output is correct
19	Correct	21 ms	97880 KB	Output is correct
20	Correct	24 ms	97880 KB	Output is correct
21	Correct	22 ms	97880 KB	Output is correct
22	Correct	21 ms	98136 KB	Output is correct
23	Incorrect	20 ms	97880 KB	Wrong Answer[1]
24	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	41 ms	97924 KB	Output is correct
2	Correct	19 ms	97880 KB	Output is correct
3	Correct	22 ms	97880 KB	Output is correct
4	Correct	21 ms	97880 KB	Output is correct
5	Correct	21 ms	97880 KB	Output is correct
6	Correct	23 ms	97880 KB	Output is correct
7	Correct	22 ms	97880 KB	Output is correct
8	Correct	21 ms	97936 KB	Output is correct
9	Correct	21 ms	98136 KB	Output is correct
10	Correct	22 ms	97984 KB	Output is correct
11	Correct	20 ms	97872 KB	Output is correct
12	Correct	19 ms	97880 KB	Output is correct
13	Correct	20 ms	97880 KB	Output is correct
14	Correct	22 ms	97932 KB	Output is correct
15	Correct	24 ms	98136 KB	Output is correct
16	Correct	21 ms	97936 KB	Output is correct
17	Correct	22 ms	97880 KB	Output is correct
18	Correct	21 ms	97916 KB	Output is correct
19	Correct	21 ms	97880 KB	Output is correct
20	Correct	24 ms	97880 KB	Output is correct
21	Correct	22 ms	97880 KB	Output is correct
22	Correct	21 ms	98136 KB	Output is correct
23	Incorrect	20 ms	97880 KB	Wrong Answer[1]
24	Halted	0 ms	0 KB	-

답안 #983515

Compilation message

Subtask #1 2.0 / 2.0

Subtask #2 10.0 / 10.0

Subtask #3 0.0 / 18.0

Subtask #4 0.0 / 30.0

Subtask #5 0.0 / 40.0

Subtask #1
2.0 / 2.0

Subtask #2
10.0 / 10.0

Subtask #3
0.0 / 18.0

Subtask #4
0.0 / 30.0

Subtask #5
0.0 / 40.0