| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 700475 |
2023-02-19T06:48:05 Z |
Nursik |
Colors (RMI18_colors) |
C++17 |
|
133 ms |
70828 KB |
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ld long double
const ll maxn = 1e6 + 1, maxm = 3e5 + 1;
const ll mod = 1e9 + 7, cmod = 998244353, inf = 1e9, blck = 400, p2 = 31;
const ld eps = 1e-9;
int t;
int n, m;
int a[maxn], b[maxn];
int used[maxn];
set<int> setik[maxn];
vector<int> g[maxn];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> t;
while (t--){
cin >> n >> m;
for (int i = 1; i <= n; ++i){
cin >> a[i];
used[a[i]] = 1;
setik[a[i]].insert(i);
}
for (int i = 1; i <= n; ++i){
cin >> b[i];
}
for (int i = 1; i < n; ++i){
int u, v;
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
int star = 0, complt = (n * (n - 1) / 2 == m);
if (complt){
vector<pair<int, int>> vec;
for (int i = 1; i <= n; ++i){
vec.pb(mp(b[i], i));
}
sort(vec.begin(), vec.end());
reverse(vec.begin(), vec.end());
int bad = 0;
for (int i = 0; i < n; ++i){
int x = vec[i].f, y = vec[i].s;
int ok = 0;
for (int j = 1; j <= n; ++j){
if (a[j] == x){
ok = 1;
a[y] = min(a[y], a[j]);
break;
}
}
bad |= !ok;
}
for (int i = 1; i <= n; ++i){
if (a[i] != b[i]){
bad = 1;
}
}
cout << "kek\n";
if (bad){
cout << 0 << '\n';
}
else{
cout << 1 << '\n';
}
for (int i = 1; i <= n; ++i){
setik[i].clear();
used[i] = 0;
g[i].clear();
}
continue;
}
for (int i = 1; i <= n; ++i){
if ((int)g[i].size() == n - 1){
star = i;
}
}
if (star){
int bad = 0;
vector<pair<int, int>> vec;
for (int i = 1; i <= n; ++i){
vec.pb(mp(b[i], i));
}
sort(vec.begin(), vec.end());
reverse(vec.begin(), vec.end());
for (int i = 0; i < n; ++i){
pair<int, int> cur = vec[i];
int x = cur.f;
int y = cur.s;
if (a[y] == b[y]){
setik[a[y]].insert(y);
continue;
}
if ((int)setik[x].size() == 0){
bad = 1;
break;
}
int z = *setik[x].begin();
setik[a[star]].erase(star);
a[star] = min(a[star], a[z]);
setik[a[star]].insert(star);
setik[a[y]].erase(y);
a[y] = min(a[y], a[star]);
setik[a[y]].insert(y);
}
for (int i = 1; i <= n; ++i){
if (a[i] != b[i]){
bad = 1;
}
}
if (bad){
cout << 0 << '\n';
}
else{
cout << 1 << '\n';
}
}
for (int i = 1; i <= n; ++i){
used[i] = 0;
g[i].clear();
setik[i].clear();
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
96 ms |
70808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
70696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
77 ms |
70784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
77 ms |
70784 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
96 ms |
70808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
133 ms |
70828 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
70792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
96 ms |
70808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
