| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 302680 |
2020-09-19T03:36:29 Z |
kevlee |
Simurgh (IOI17_simurgh) |
C++17 |
|
1 ms |
384 KB |
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mod 1000000007
#define h1 7897897897897897
#define h2 7897466719774591
#define b1 98762051
#define b2 98765431
#define inf 1000000000
#define pi 3.1415926535897932384626
#define LMAX 9223372036854775807
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pii>
#define SET(a, b) memset(a, b, sizeof(a))
#define all(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
vi ans;
int m;
vp edges[505];
vi nodes[505];
int group[505];
bool used[505];
int f(int x) {
return x == group[x] ? x : group[x] = f(group[x]);
}
vi find_roads(int n, vi u, vi v) {
m = u.size();
FOR(i, 0, m-1) {
edges[u[i]].emplace_back(v[i], i);
edges[v[i]].emplace_back(u[i], i);
}
FOR(i, 0, n-1) {
int sz = edges[i].size();
if (sz == 1) {
ans.pb(edges[i][0].se);
continue;
}
FOR(j, 0, n-1) group[j] = j;
vi query;
FOR(j, 0, m-1) {
if (u[j] == i || v[j] == i) continue;
int x = f(u[j]);
int y = f(v[j]);
if (x != y) {
query.pb(j);
group[x] = y;
}
}
FOR(j, 0, n-1) nodes[j].clear();
FOR(j, 0, edges[i].size() - 1) {
nodes[f(edges[i][j].fi)].pb(edges[i][j].fi);
}
FOR(k, 0, n-1) {
//cout << i <<" "<<k << " " << nodes[k].size() << endl;
if (nodes[k].size() == 0 || k == i) continue;
vp res;
vi ask = query;
FOR(j, 0, n-1) used[j] = false;
used[k] = used[i] = true;
vi candidate;
FOR(j, 0, edges[i].size() - 1) {
int x = f(edges[i][j].fi);
if (!used[x]) {
used[x] = true;
ask.pb(edges[i][j].se);
} else if (x == k) {
candidate.pb(edges[i][j].se);
}
}
for (auto it: candidate) {
ask.pb(it);
//for (auto q: ask) cout << q <<' ';
//cout << endl;
int cnt = count_common_roads(ask);
res.pb({cnt, it});
ask.pop_back();
}
sort(res.rbegin(), res.rend());
for (auto p: res) {
if (p.fi != res[0].fi) {
break;
}
ans.pb(p.se);
}
}
}
sort(all(ans));
auto iter = unique(all(ans));
ans.resize(distance(ans.begin(), iter));
for (auto it: ans) cout << it << ' ' ;
cout << endl;
return ans;
}
Compilation message
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:23:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | #define FOR(i, a, b) for (int i = (a); i <= (b); i++)
| ^
simurgh.cpp:58:5: note: in expansion of macro 'FOR'
58 | FOR(j, 0, edges[i].size() - 1) {
| ^~~
simurgh.cpp:23:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | #define FOR(i, a, b) for (int i = (a); i <= (b); i++)
| ^
simurgh.cpp:69:7: note: in expansion of macro 'FOR'
69 | FOR(j, 0, edges[i].size() - 1) {
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Security Violation! Don't try to hack |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Security Violation! Don't try to hack |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Security Violation! Don't try to hack |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Security Violation! Don't try to hack |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Security Violation! Don't try to hack |
| 2 |
Halted |
0 ms |
0 KB |
- |
