#include "highway.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define szof(s) (int)s.size()
#define ll long long
#define fr first
#define sc second
using namespace std;
const int N = 90004;
vector <int> g[N];
int x[N], y[N];
int n, m, a, b;
int S, T;
vector <int> w;
map <pii, bool> mp;
struct SmallSolve {
int dfs(int v, int par) {
for (int to : g[v]) {
if (to == par) {
continue;
}
if (mp.count({v, to})) {
return dfs(to, v);
}
}
return v;
}
void solve(int NN, vector<int> U, vector<int> V, int A, int B) {
n = NN;
m = U.size();
a = A;
b = B;
w.resize(m, 1);
for (int i = 0; i < m; i++) {
x[i] = U[i];
y[i] = V[i];
g[x[i]].push_back(y[i]);
g[y[i]].push_back(x[i]);
}
ll before = ask(w);
for (int i = 0; i < m; i++) {
w[i] = 0;
int nxt = ask(w);
if (nxt < before) {
w[i] = 0;
before = nxt;
} else {
w[i] = 1;
}
}
for (int i = 0; i < m; i++) {
if (w[i] == 0) {
mp[{x[i], y[i]}] = 1;
mp[{y[i], x[i]}] = 1;
}
}
S = 0;
T = dfs(0, -1);
answer(S, T);
}
}subtask1;
void find_pair(int NN, vector<int> U, vector<int> V, int A, int B) {
if (NN <= 100 && szof(U) == NN - 1) {
subtask1.solve(NN, U, V, A, B);
} else {
}
}
/*
10
9
4
9
4
1
4 6
9 5
5 0
8 2
1 7
7 4
4 2
2 9
3 9
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2432 KB |
Output is correct |
2 |
Correct |
3 ms |
2432 KB |
Output is correct |
3 |
Correct |
4 ms |
2432 KB |
Output is correct |
4 |
Correct |
4 ms |
2432 KB |
Output is correct |
5 |
Correct |
3 ms |
2432 KB |
Output is correct |
6 |
Correct |
3 ms |
2432 KB |
Output is correct |
7 |
Correct |
3 ms |
2432 KB |
Output is correct |
8 |
Correct |
2 ms |
2500 KB |
Output is correct |
9 |
Correct |
3 ms |
2432 KB |
Output is correct |
10 |
Correct |
3 ms |
2432 KB |
Output is correct |
11 |
Correct |
3 ms |
2432 KB |
Output is correct |
12 |
Correct |
3 ms |
2432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2432 KB |
Output is incorrect: answered not exactly once. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
12 ms |
2560 KB |
Output is incorrect: answered not exactly once. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2432 KB |
Output is incorrect: answered not exactly once. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
11 ms |
2560 KB |
Output is incorrect: answered not exactly once. |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
10 ms |
2560 KB |
Output is incorrect: answered not exactly once. |
2 |
Halted |
0 ms |
0 KB |
- |