oj.uz

Submission #1108609

# Submission time Handle Problem Language Result Execution time Memory
1108609 2024-11-04T15:13:41 Z LinhLewLew Colors (RMI18_colors) C++17
32 / 100
 142 ms 31736 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 : par[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

# Verdict Execution time Memory Grader output
1 Correct 77 ms 31312 KB Output is correct
2 Correct 26 ms 31312 KB Output is correct
3 Correct 9 ms 31568 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 31732 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 31312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 31312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 31312 KB Output is correct
2 Correct 26 ms 31312 KB Output is correct
3 Correct 9 ms 31568 KB Output is correct
4 Incorrect 53 ms 31312 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 142 ms 31312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 31312 KB Output is correct
2 Correct 14 ms 31696 KB Output is correct
3 Correct 12 ms 31736 KB Output is correct

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 31312 KB Output is correct
2 Correct 26 ms 31312 KB Output is correct
3 Correct 9 ms 31568 KB Output is correct
4 Correct 44 ms 31732 KB Output is correct
5 Incorrect 53 ms 31312 KB Output isn't correct
6 Halted 0 ms 0 KB -