oj.uz

답안 #1108620

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1108620 2024-11-04T15:49:26 Z LinhLewLew Colors (RMI18_colors) C++17
100 / 100
 435 ms 96952 KB 
// PhuThuyRuntime <3
// A secret makes a woman woman

#include <bits/stdc++.h>

using namespace std;

#define eb emplace_back
#define ef emplace_front
#define pb push_back
#define pf push_front
#define all(v) v.begin(), v.end()
#define ins insert
#define lb lower_bound
#define ub upper_bound
#define fo(i, l, r) for(int i = l; i <= r; i++)
#define foi(i, l, r) for(int i = l; i >= r; i--)
#define elif else if
#define el cout << "\n";
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define pil pair<int, ll>
#define fi first
#define se second
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#define ll long long
#define ull unsigned long long
#define pob pop_back
#define bs binary_search
#define vi vector<int>
#define vii vector<pair<int, int>>
#define getbit(i, j) (i >> j) & 1
#define offbit(i, j) (1 << j) ^ i
#define onbit(i, j) (1 << j) | i
const int N = 1e5 + 2;
const ll mod = 1e9 + 7;
const int inf = INT_MAX;
const int base = 31;
const long double EPS = 1e-9;
const long double pi = acos(-1.0);
int t, n, m, a[2 * N], b[2 * N];
vi adjA[2 * N], adjB[2 * N];
vii edges, e[8 * N];
void inp(){
     cin >> n >> m;
     edges.clear();
     fo(i, 1, n) adjA[i].clear(), adjB[i].clear();
     fo(i, 1, 4 * n) e[i].clear();
     fo(i, 1, n){
          cin >> a[i];
          adjA[a[i]].eb(i);
     }
     fo(i, 1, n){
          cin >> b[i];
          adjB[b[i]].eb(i);
     }
     fo(i, 1, m){
          int u, v; cin >> u >> v;
          edges.eb(u, v);
     }
}
struct zata{
     int x, y, xSize, ySize;
};
stack<zata> st;

struct dsu{
     int par[2 * N], sz[2 * N];
     void makeset(int u){
          par[u] = u;
          sz[u] = 1;
     }
     int findset(int u){
          return u == par[u] ? u : findset(par[u]);
     }
     void joinset(int u, int v){
          u = findset(u);
          v = findset(v);
          if(u == v) return;
          if(sz[u] < sz[v]) swap(u, v);
          st.push({u, v, sz[u], sz[v]});
          par[v] = u;
          sz[u] += sz[v];
     }
     void rollback(int SZ) {
          while ((int)st.size() > SZ) {
               zata top = st.top();
               st.pop();
               par[top.x] = top.x;
               par[top.y] = top.y;
               sz[top.x] = top.xSize;
               sz[top.y] = top.ySize;
          }
     }

} dsu;

void update(int id, int l, int r, int u, int v, pii edge){
     if(l > v || r < u) return;
     if(u <= l && r <= v){
          e[id].eb(edge);
          return;
     }
     int m = l + r >> 1;
     update(id << 1, l, m, u, v, edge);
     update(id << 1 | 1, m + 1, r, u, v, edge);
}
int ans;
void solve(int id, int l, int r) {
     int sz = (int)st.size();
     for (auto [u, v] : e[id]) dsu.joinset(u, v);
     if (l == r){
          unordered_set<int> cnt;
          for (auto x : adjA[l]) cnt.insert(dsu.findset(x));
          for (auto x : adjB[l]) {
               if (!cnt.count(dsu.findset(x))) ans = 0;
          }
     }
     else {
          int m = (l + r) / 2;
          solve(id << 1, l, m);
          solve(id << 1 | 1, m + 1, r);
     }
     dsu.rollback(sz);
}
void sol(){
     fo(i, 1, n){
          if(a[i] < b[i]){
               cout << 0, el
               return;
          }
     }
     for(auto [u, v] : edges){
          int mn = max(b[u], b[v]);
          int mx = min(a[u], a[v]);
          if(mn <= mx) update(1, 1, n, mn, mx, {u, v});
     }
     ans = 1;
     solve(1, 1, n);
     cout << ans, el
}
int main(){
     ios_base::sync_with_stdio(false);
     cin.tie(NULL);
     fo(i, 1, 200000) dsu.makeset(i);
     cin >> t;
     while(t--){
          inp();
          sol();
     }
     return 0;
}

Compilation message

colors.cpp: In function 'void update(int, int, int, int, int, std::pair<int, int>)':
colors.cpp:106:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |      int m = l + r >> 1;
      |              ~~^~~

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 31312 KB Output is correct
2 Correct 28 ms 31512 KB Output is correct
3 Correct 8 ms 31568 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 31436 KB Output is correct
2 Correct 23 ms 31824 KB Output is correct
3 Correct 9 ms 31684 KB Output is correct

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 31436 KB Output is correct
2 Correct 23 ms 31824 KB Output is correct
3 Correct 9 ms 31684 KB Output is correct
4 Correct 105 ms 34376 KB Output is correct
5 Correct 230 ms 52900 KB Output is correct
6 Correct 407 ms 73920 KB Output is correct

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 31312 KB Output is correct
2 Correct 28 ms 31512 KB Output is correct
3 Correct 8 ms 31568 KB Output is correct
4 Correct 54 ms 31436 KB Output is correct
5 Correct 23 ms 31824 KB Output is correct
6 Correct 9 ms 31684 KB Output is correct
7 Correct 56 ms 32840 KB Output is correct
8 Correct 28 ms 31960 KB Output is correct
9 Correct 9 ms 31736 KB Output is correct

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 31312 KB Output is correct
2 Correct 262 ms 53804 KB Output is correct
3 Correct 243 ms 63928 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 31312 KB Output is correct
2 Correct 13 ms 31824 KB Output is correct
3 Correct 9 ms 31568 KB Output is correct

Subtask #8
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 31312 KB Output is correct
2 Correct 28 ms 31512 KB Output is correct
3 Correct 8 ms 31568 KB Output is correct
4 Correct 44 ms 31580 KB Output is correct
5 Correct 54 ms 31436 KB Output is correct
6 Correct 23 ms 31824 KB Output is correct
7 Correct 9 ms 31684 KB Output is correct
8 Correct 105 ms 34376 KB Output is correct
9 Correct 230 ms 52900 KB Output is correct
10 Correct 407 ms 73920 KB Output is correct
11 Correct 56 ms 32840 KB Output is correct
12 Correct 28 ms 31960 KB Output is correct
13 Correct 9 ms 31736 KB Output is correct
14 Correct 105 ms 31312 KB Output is correct
15 Correct 262 ms 53804 KB Output is correct
16 Correct 243 ms 63928 KB Output is correct
17 Correct 24 ms 31312 KB Output is correct
18 Correct 13 ms 31824 KB Output is correct
19 Correct 9 ms 31568 KB Output is correct
20 Correct 68 ms 34100 KB Output is correct
21 Correct 275 ms 56444 KB Output is correct
22 Correct 435 ms 96952 KB Output is correct