# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
872186 | Matjaz | Parachute rings (IOI12_rings) | C++14 | 4040 ms | 33320 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 <vector>
#include <queue>
using namespace std;
int N;
vector<vector<int> > s;
void Init(int N_) {
N = N_;
s.assign(N, vector <int> ());
}
void Link(int A, int B) {
s[A].push_back(B);
s[B].push_back(A);
}
int CountCritical() {
int res = 0;
for (int t=0;t<N;t++){
vector<int> d(N);
for (int i=0;i<N;i++) d[i] = s[i].size();
for (int i=0;i<s[t].size();i++) d[s[t][i]]--;
vector<int> found(N, 0);
bool critical = true;
for (int i=0;i<N;i++){
if (i == t) continue;
if (found[i]) continue;
found[i] = true;
if (d[i] == 0) continue;
int countOne = 0;
queue<int> Q;
Q.push(i);
while (!Q.empty()){
int x = Q.front();Q.pop();
if (d[x] > 2){
critical = false;
break;
}
if (d[x] == 1) countOne++;
for (int i=0;i<s[x].size();i++){
if (s[x][i] == t) continue;
if (found[s[x][i]]) continue;
found[s[x][i]] = true;
Q.push(s[x][i]);
}
}
if (countOne != 2) critical = false;
}
if (critical) res++;
}
return res;
}
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... |