Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <cmath>
- #include <climits>
- using namespace std;
- struct puperfunctionmycreateion {
- int data, prev, st, ans;
- bool bol;
- };
- int find228(queue <puperfunctionmycreateion>, int);
- int find1337(queue <puperfunctionmycreateion>, int);
- int view(vector <int>);
- puperfunctionmycreateion check(queue <puperfunctionmycreateion>, int);
- int main()
- {
- puperfunctionmycreateion temp, temp1, pituh2281337332;
- int n, m, free = 0, v, u, h, data1;
- vector <int> a, ans, mark, ans1;
- vector <vector <int> > dp;
- queue <puperfunctionmycreateion> q;
- cin >> n >> m;
- mark.reserve(n + 1);
- a.reserve(n + 1);
- ans.reserve(n + 1);
- ans.resize(n + 1);
- a.resize(n + 1);
- mark.resize(n + 1);
- dp.reserve(n + 1);
- dp.resize(n + 1);
- for (int i = 1; i <= n; i++){
- mark[i] = 0;
- ans[i] = INT_MAX - 20;
- cin >> a[i];
- if (a[i] != 0) {
- temp.data = i;
- temp.st = i;
- temp.ans = 0;
- temp.prev = 0;
- q.push(temp);
- mark[i] = 1;
- }
- }
- for (int i = 1; i <= n; i++) {
- cin >> v >> u;
- dp[v - 1].push_back(u);
- dp[u - 1].push_back(v);
- }
- while (!q.empty()) {
- temp = q.front();
- q.pop();
- for (int i = 0; i < dp[temp.data - 1].size(); i++){
- data1 = dp[temp.data - 1][i];
- if (data1 != temp.prev)
- if (!mark[data1]) {
- temp1.data = data1;
- temp1.st = temp.st;
- temp1.ans = temp.ans + 1;
- temp1.prev = temp.data;
- q.push(temp1);
- mark[data1] = 1;
- }
- else {
- pituh2281337332 = check(q, data1);
- if (pituh2281337332.bol)
- if (a[temp.st] != a[pituh2281337332.st])
- if (a[data1] == 0){
- ans[temp.st] = min(ans[temp.st], temp.ans + pituh2281337332.ans + 1);
- ans[pituh2281337332.st] = min(ans[pituh2281337332.st], ans[temp.st]);
- }
- else{
- ans[data1] = min(ans[data1], temp.ans + 1);
- ans[pituh2281337332.st] = min(ans[pituh2281337332.st], ans[temp.st]);
- }
- }
- }
- }
- int min2;
- min2 = ans[1];
- for (int i = 2; i <= n; i++)
- min2 = min(min2, ans[i]);
- cout << min2 << "\n";
- return 0;
- }
- puperfunctionmycreateion check(queue <puperfunctionmycreateion> f, int data1){
- int st, ans1 = -1, ans2;
- puperfunctionmycreateion ans5;
- while (!f.empty()) {
- if (f.front().data == data1){
- ans1 = f.front().data;
- st = f.front().st;
- ans2 = f.front().ans;
- }
- f.pop();
- }
- ans5.st = st;
- ans5.bol = (ans1 != -1);
- ans5.ans = ans2;
- return ans5;
- }
- int view(vector <int> b) {
- for (int i = 1; i <= b.size(); i++)
- cout << b[i] << endl;
- cout << "end\n";
- return 0;
- }
- /*
- 16 24
- 2 0 0 0 0 0 0 4 0 1 0 0 0 0 0 0
- 1 2
- 1 3
- 1 4
- 1 7
- 2 4
- 2 7
- 2 5
- 2 6
- 3 4
- 4 7
- 5 8
- 5 9
- 5 10
- 5 11
- 6 12
- 6 13
- 6 14
- 6 15
- 6 16
- 12 5
- 13 5
- 14 5
- 15 5
- 16 5*/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement