oj.uz

답안 #701771

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
701771 2023-02-22T05:28:09 Z Nursik Colors (RMI18_colors) C++14
100 / 100
 689 ms 200084 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, blcok = 400, p2 = 31;
const ld eps = 1e-9;
 
int t;
int n, m, z, bad;
int a[maxn], b[maxn], is[maxn];
int u[maxn], v[maxn];
vector<pair<int, int>> tree[maxn * 4];
vector<int> nur[maxn], sik[maxn];
struct dsu{
    int p[maxn], sz[maxn];
    stack<pair<int, int>> st;
    void init(){
        for (int i = 1; i <= n; ++i){
            p[i] = i, sz[i] = 1;
        }
    }
    int get(int v){
        if (v == p[v])
            return v;
        return get(p[v]);
    }
    void unite(int a, int b){
        a = get(a), b = get(b);
        if (a == b){
            return;
        }
        if (sz[a] > sz[b])
            swap(a, b);
        p[a] = b;
        sz[b] += sz[a];
        st.push(mp(a, sz[a]));
    }
    void rollback(){
        pair<int, int> cur = st.top();
        int x = cur.f, y = cur.s;
        sz[p[x]] -= y;
        p[x] = x;
        st.pop();
    }
} rt;
void upd(int l, int r, int k, int vr = 1, int tl = 1, int tr = n){
    if (l <= tl && tr <= r){
        tree[vr].pb(mp(u[k], v[k]));
        return;
    }
    if (l > tr || r < tl)
        return;
    int tm = (tl + tr) / 2;
    upd(l, r, k, vr + vr, tl, tm);
    upd(l, r, k, vr + vr + 1, tm + 1, tr);
}
void solve(int v = 1, int tl = 1, int tr = n){
    int stz = rt.st.size();
    for (auto it : tree[v]){
        int x = it.f, y = it.s;
        rt.unite(x, y);
    }
    if (tl == tr){
        ++z;
        for (auto it : nur[tl]){
            int root = rt.get(it);
            is[root] = z;
        }
        for (auto it : sik[tl]){
            int root = rt.get(it);
            if (is[root] != z){
                bad = 1;
            }
        }
    }
    else{
        int tm = (tl + tr) / 2;
        solve(v + v, tl, tm);
        solve(v + v + 1, tm + 1, tr);
    }
    while (rt.st.size() > stz){
        rt.rollback();
    }
    tree[v].clear();
    nur[tl].clear();
    sik[tl].clear();
}
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];
            nur[a[i]].pb(i);
        }
        for (int i = 1; i <= n; ++i){
            cin >> b[i];
            sik[b[i]].pb(i);
        }
        bad = 0;
        for (int i = 1; i <= m; ++i){
            cin >> u[i] >> v[i];
            int l = max(b[u[i]], b[v[i]]);
            int r = min(a[u[i]], a[v[i]]);
            upd(l, r, i);
        }
        rt.init();
        solve();
        if (bad){
            cout << 0 << '\n';
        }
        else{
            cout << 1 << '\n';
        }
    }
}
/*
*/

Compilation message

colors.cpp: In function 'void solve(int, int, int)':
colors.cpp:113:25: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  113 |     while (rt.st.size() > stz){
      |            ~~~~~~~~~~~~~^~~~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 142668 KB Output is correct
2 Correct 91 ms 141876 KB Output is correct
3 Correct 67 ms 141620 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 143108 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 142668 KB Output is correct
2 Correct 88 ms 141860 KB Output is correct
3 Correct 70 ms 141500 KB Output is correct

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 142668 KB Output is correct
2 Correct 88 ms 141860 KB Output is correct
3 Correct 70 ms 141500 KB Output is correct
4 Correct 180 ms 144356 KB Output is correct
5 Correct 439 ms 163460 KB Output is correct
6 Correct 689 ms 184732 KB Output is correct

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 142668 KB Output is correct
2 Correct 91 ms 141876 KB Output is correct
3 Correct 67 ms 141620 KB Output is correct
4 Correct 122 ms 142668 KB Output is correct
5 Correct 88 ms 141860 KB Output is correct
6 Correct 70 ms 141500 KB Output is correct
7 Correct 120 ms 142692 KB Output is correct
8 Correct 87 ms 141852 KB Output is correct
9 Correct 70 ms 141548 KB Output is correct

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 182 ms 144392 KB Output is correct
2 Correct 413 ms 164024 KB Output is correct
3 Correct 410 ms 175652 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 142028 KB Output is correct
2 Correct 74 ms 141964 KB Output is correct
3 Correct 72 ms 141460 KB Output is correct

Subtask #8
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 142668 KB Output is correct
2 Correct 91 ms 141876 KB Output is correct
3 Correct 67 ms 141620 KB Output is correct
4 Correct 118 ms 143108 KB Output is correct
5 Correct 122 ms 142668 KB Output is correct
6 Correct 88 ms 141860 KB Output is correct
7 Correct 70 ms 141500 KB Output is correct
8 Correct 180 ms 144356 KB Output is correct
9 Correct 439 ms 163460 KB Output is correct
10 Correct 689 ms 184732 KB Output is correct
11 Correct 120 ms 142692 KB Output is correct
12 Correct 87 ms 141852 KB Output is correct
13 Correct 70 ms 141548 KB Output is correct
14 Correct 182 ms 144392 KB Output is correct
15 Correct 413 ms 164024 KB Output is correct
16 Correct 410 ms 175652 KB Output is correct
17 Correct 99 ms 142028 KB Output is correct
18 Correct 74 ms 141964 KB Output is correct
19 Correct 72 ms 141460 KB Output is correct
20 Correct 148 ms 144044 KB Output is correct
21 Correct 402 ms 166944 KB Output is correct
22 Correct 651 ms 200084 KB Output is correct