| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 557941 | FatihSolak | Colors (RMI18_colors) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define N 200005
#define M 3005
using namespace std;
int a[N];
int b[N];
vector<int> adj[N];
set<int> s[N];
bool ok[N];
bool can[N][N];
void dfs(int v,int par){
s[v] = {a[v]};
for(auto u:adj[v]){
if(u == par)continue;
dfs(u,v);
if(s[v].size() < s[u].size())
swap(s[v],s[u]);
for(auto c:s[u])
s[v].insert(c);
}
while(*s[v].begin() < b[v])
s[v].erase(*s[v].begin());
while(*s[v].rbegin() > a[v])
s[v].erase(*s[v].rbegin());
if(s[v].count(b[v]))
ok[v] = 1;
}
void solve(){
int n,m;
cin >> n >> m;
for(int i = 1;i<=n;i++){
cin >> a[i];
adj[i].clear();
ok[i] = 0;
}
for(int i = 1;i<=n;i++){
cin >> b[i];
}
for(int i = 1;i<=m;i++){
int u,v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i = 1;i<=n;i++){
if(a[i] < b[i]){
cout << 0 << endl;
return;
}
}
if(m == 1ll*n*(n-1)/2){
map<int,int> ok;
for(int i = 1;i<=n;i++){
ok[a[i]] = 1;
}
for(int i = 1;i<=n;i++){
if(!ok[b[i]]){
cout << 0 << endl;
return;
}
}
cout << 1 << endl;
return;
}
if(m == n-1){
bool ck = 1;
for(int i = 1;i<=n;i++){
if(adj[i].size() > 2)ck = 0;
}
if(n < 10)ck = 0;
for(int i = 1;i<=n;i++){
if(!ck || (adj[i].size() == 1))
dfs(i,0);
}
for(int i = 1;i<=n;i++){
if(!ok[i]){
cout << 0 << endl;
return;
}
}
cout << 1 << endl;
return;
}
for(int i = 1;i<=n;i++){
for(int j = 1;j<=n;j++){
can[i][j] = 0;
}
can[i][a[i]] = 1;
}
for(int i = 1;i<=n;i++){
queue<int> q;
for(int j = 1;j<=n;j++){
if(a[j] == i)q.push(j);
}
while(q.size()){
auto tp = q.front();
q.pop();
for(auto u:adj[v]){
if(a[u] > i && b[u] <= i && !can[u][i]){
can[u][i] = 1;
q.push(u);
}
}
}
}
for(int i = 1;i<=n;i++){
if(!can[i][b[i]]){
cout << 0 << endl;
return;
}
}
cout << 1 << endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef Local
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t = 1;
cin >> t;
while(t--){
solve();
}
#ifdef Local
cout << endl << fixed << setprecision(2) << 1000.0*clock()/CLOCKS_PER_SEC << " milliseconds.";
#endif
}