| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 838792 |
2023-08-27T18:36:09 Z |
ErJ |
Keys (IOI21_keys) |
C++17 |
|
3000 ms |
30968 KB |
#include <vector>
#include <unordered_map>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
typedef long long ll;
vector<vector<pair<int, int>>> edges; //kam, key
vector<int> p, r;
vector<vector<int>> kv;//potrebuji klic na hranu vedouci do vrcholu
vector<bool> was;
int DFS(int u) {
int ans = 0;
queue<int> q;
q.push(u);
was[u] = true;
kv[r[u]][0] = -2;
while (!q.empty()) {
int v = q.front();
q.pop();
for (int i = 0; i < edges[v].size(); i++) {
//cout << i << endl;
int w = edges[v][i].first;
int kw = edges[v][i].second;
if (kv[kw][0] == -2) {
if (!was[w]) {
was[w] = true;
q.push(w);
ans++;
if (kv[r[w]][0] != -2) {
kv[r[w]][0] = -2;
for (int i = 1; i < kv[r[w]].size(); i++) {
int x = kv[r[w]][i];
if (!was[x]) {
was[x] = true;
q.push(x);
ans++;
}
}
}
}
}
else {
if(!was[w]) kv[kw].push_back(w);
}
}
}
return ans;
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
int n = r.size();
int m = u.size();
edges.resize(n);
for (int i = 0; i < m; i++) {
edges[u[i]].push_back({ v[i], c[i] });
edges[v[i]].push_back({ u[i], c[i] });
}
p.resize(n);
::r = r;
int MIN = 1000000009;
//cout << "ahoj" << endl;
for (int i = 0; i < n; i++) {
//cout << "ahoj" << i << endl;
kv.clear();
was.clear();
kv.resize(n);
was.resize(n);
for (int j = 0; j < n; j++) {
kv[j].push_back(-1);
was[j] = false;
}
p[i] = DFS(i);
MIN = min(MIN, p[i]);
}
//cout << "ahojda" << endl;
vector<int> ans(n);
for (int i = 0; i < n; i++) {
//cout << p[i] << endl;
if (p[i] == MIN) {
ans[i] = 1;
}
else {
ans[i] = 0;
}
}
return ans;
}
Compilation message
keys.cpp: In function 'int DFS(int)':
keys.cpp:26:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | for (int i = 0; i < edges[v].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
keys.cpp:37:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for (int i = 1; i < kv[r[w]].size(); i++) {
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
2 ms |
212 KB |
Output is correct |
| 9 |
Correct |
2 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
2 ms |
212 KB |
Output is correct |
| 9 |
Correct |
2 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
2 ms |
212 KB |
Output is correct |
| 9 |
Correct |
2 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
2 ms |
212 KB |
Output is correct |
| 9 |
Correct |
2 ms |
212 KB |
Output is correct |
| 10 |
Execution timed out |
3048 ms |
30968 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
2 ms |
212 KB |
Output is correct |
| 9 |
Correct |
2 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
