# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
983477 | Alkaser_ID | Game (APIO22_game) | C++17 | 9 ms | 30324 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "game.h"
using namespace std;
#include <bits/stdc++.h>
int res = 0,K=0;
set<int> scc[300005],rv[300005];
int c[300005]; bool b[300005];
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[300005]; set<int> s; int sp = 0;
vector<int> cv;
inline void cycle() {
int C = *s.begin();
for(set<int>::iterator it = s.begin();it!=s.end();++it) {
//cout << *it << " e " << endl;
//if(*it < K) ++sp;
}
//cout << endl;
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);
//cout << "Sp " << sp << endl;
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()) {
//cout << "HI\n";
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();
//cout << res << endl;
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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |