| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 851811 |
2023-09-20T16:17:11 Z |
TimDee |
Colors (RMI18_colors) |
C++17 |
|
0 ms |
0 KB |
// Esti <3
//\
šťastia pre nás :)
// you're already the best
// _
// ^ ^ //
// >(O_O)<___//
// \ __ __ \
// \\ \\ \\\\
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//#define int long long
#define forn(i,n) for(int i=0; i<(n); ++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second
#define vii(a,n) vector<int> a(n); forn(i,n) cin>>a[i];
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int inf = 1e18;
const int mod = 998244353;
// \
\
:smiling_face_with_3_hearts: :smiling_face_with_3_hearts: :smiling_face_with_3_hearts:
//vidime sa veľmi skoro, moje slnko
const int N = 2e5+5;
int n,m;
int a[N], b[N];
pi e[N];
int is[N], r[N];
vector<pi> adj[N];
bitset<N> vis;
bitset<N> ok;
vector<int> adj[N];
int dfs(int u, int x) {
if (a[u] < x) return 0;
if (a[u]==x) return 1;
if (vis[u]) return 0;
if (ok[u]) return 0;
vis[u]=1;
for(auto&v:adj[u]) {
dfs(v,x);
if (a[v]==x) a[u]=x;
}
return a[u]==x;
}
int can(int s, int x) {
vis.reset();
return dfs(s,x);
}
void bad() {
forn(i,n) adj[i].clear();
ok.reset();
forn(i,m) {
int u=e[i].f, v=e[i].s; --u, --v;
adj[u].pb(v);
adj[v].pb(u);
}
vector<pi> v;
forn(i,n) v.pb({b[i],i});
sort(rall(v));
for(auto&x:v) {
int z = can(x.s, x.f);
if (!z) {
cout<<"0\n"; return;
}
ok[x.s]=1;
}
cout<<"1\n";
}
struct DSU {
vector<int> p,sz,mn;
vector<pi> rb;
void init(int n) {
p.clear(); sz.clear(); mn.clear(); rb.clear();
forn(i,n) p.pb(i), sz.pb(1), mn.pb(a[i]);
}
int get(int u) {
return p[u]==u?u:get(p[u]);
}
void uni(int u, int v) {
u=get(u), v=get(v);
if (u==v) {
rb.pb({-1,-1}); return;
}
if (sz[u]<sz[v]) swap(u,v);
p[v]=u;
sz[u]+=sz[v];
rb.pb({v,mn[u]});
mn[u]=min(mn[u],mn[v]);
}
void roll() {
auto it = rb.back(); rb.pop_back();
int v = it.f, old = it.s;
int u = p[v];
p[v] = v;
sz[u] -= sz[v];
mn[u] = old;
}
};
DSU dsu;
struct sgt {
vector<vector<int>> t; int sz=1;
int l,r,v;
void init(int n) {
t.clear();
sz=1;
while (sz<n) sz<<=1;
t.resize(2*sz);
l=0, r=sz, v=0;
}
void add(int v, int l, int r, int lx, int rx, int i) {
if (rx<=l || r<=lx) return;
if (lx<=l && r<=rx) {
t[v].pb(i); return;
}
int m=(l+r)>>1;
add(2*v+1,l,m,lx,rx,i);
add(2*v+2,m,r,lx,rx,i);
}
void add(int l, int r, int i) {
add(0,0,sz,l,r,i);
}
void go(int i) {
while (r<=i) {
if (v&1) r+=r-l;
else l-=r-l;
for(auto&x:t[v]) dsu.roll();
v = (v-1)>>1;
}
while (r-l > 1) {
int m = (l+r)>>1;
if (i<m) {
r=m;
v=2*v+1;
} else {
l=m;
v=2*v+2;
}
for(auto&x:t[v]) dsu.uni(e[x].f, e[x].s);
}
}
};
sgt st;
void solve() {
cin>>n>>m;
forn(i,n) cin>>a[i];
forn(i,n) cin>>b[i];
forn(i,m) cin>>e[i].f>>e[i].s;
forn(i,n) {
if (a[i]<b[i]) {
cout<<"0\n"; return;
}
}
if (n<=5000) {
bad(); return;
}
forn(i,n) adj[i].clear();
forn(i,m) is[i]=r[i]=0;
dsu.init(n+5);
st.init(n+5);
forn(i,m) {
--e[i].f, --e[i].s;
int u=e[i].f, v=e[i].s;
adj[u].pb({v,i});
adj[v].pb({u,i});
}
vector<vector<int>> A(n+1), B(n+1);
forn(i,n) A[a[i]].pb(i);
forn(i,n) B[b[i]].pb(i);
for (int i=n; i>0; --i) {
for(auto&u:A[i]) {
for(auto&e:adj[u]) {
int v = e.s, j = e.s;
if (is[j]>=2) continue;
is[j]++;
if (is[j]==2) r[j] = i+1;
//cout<<"! "<<j<<' '<<i+1<<'\n';
}
}
for(auto&u:B[i]) {
for(auto&e:adj[u]) {
int v = e.s, j = e.s;
if (is[j]<2) {
is[j]=4; continue;
}
if (is[j]>2) continue;
is[j]=3;
st.add(i, r[j], j);
//cout<<j<<": "<<::e[j].f<<' '<<::e[j].s<<" "<<i<<' '<<r[j]<<'\n';
}
}
}
for (int i=1; i<=n; ++i) {
st.go(i);
//cout<<"! "<<i<<": ";
//forn(j,n) cout<<dsu.get(j)<<' '; cout<<'\n';
for(auto&u:B[i]) {
int p = dsu.get(u);
int m = dsu.mn[p];
if (m != i) {
cout<<"0\n"; return;
}
}
}
cout<<"1\n";
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t=1;
cin>>t;
while (t--) solve();
return 0;
}
Compilation message
colors.cpp:3:1: warning: multi-line comment [-Wcomment]
3 | //\
| ^
colors.cpp:9:1: warning: multi-line comment [-Wcomment]
9 | // \ __ __ \
| ^
colors.cpp:30:1: warning: multi-line comment [-Wcomment]
30 | // \
| ^
colors.cpp:27:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
27 | const int inf = 1e18;
| ^~~~
colors.cpp:46:13: error: conflicting declaration 'std::vector<int> adj [200005]'
46 | vector<int> adj[N];
| ^~~
colors.cpp:42:12: note: previous declaration as 'std::vector<std::pair<int, int> > adj [200005]'
42 | vector<pi> adj[N];
| ^~~
colors.cpp: In function 'int dfs(int, int)':
colors.cpp:55:7: error: cannot convert 'std::pair<int, int>' to 'int'
55 | dfs(v,x);
| ^
| |
| std::pair<int, int>
colors.cpp:48:13: note: initializing argument 1 of 'int dfs(int, int)'
48 | int dfs(int u, int x) {
| ~~~~^
colors.cpp:56:8: error: no match for 'operator[]' (operand types are 'int [200005]' and 'std::pair<int, int>')
56 | if (a[v]==x) a[u]=x;
| ^
colors.cpp: In function 'void bad()':
colors.cpp:72:14: error: no matching function for call to 'std::vector<std::pair<int, int> >::push_back(int&)'
72 | adj[u].pb(v);
| ^
In file included from /usr/include/c++/10/vector:67,
from /usr/include/c++/10/functional:62,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from colors.cpp:12:
/usr/include/c++/10/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, int>]'
1187 | push_back(const value_type& __x)
| ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1187:35: note: no known conversion for argument 1 from 'int' to 'const value_type&' {aka 'const std::pair<int, int>&'}
1187 | push_back(const value_type& __x)
| ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, int>]'
1203 | push_back(value_type&& __x)
| ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1203:30: note: no known conversion for argument 1 from 'int' to 'std::vector<std::pair<int, int> >::value_type&&' {aka 'std::pair<int, int>&&'}
1203 | push_back(value_type&& __x)
| ~~~~~~~~~~~~~^~~
colors.cpp:73:14: error: no matching function for call to 'std::vector<std::pair<int, int> >::push_back(int&)'
73 | adj[v].pb(u);
| ^
In file included from /usr/include/c++/10/vector:67,
from /usr/include/c++/10/functional:62,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from colors.cpp:12:
/usr/include/c++/10/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, int>]'
1187 | push_back(const value_type& __x)
| ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1187:35: note: no known conversion for argument 1 from 'int' to 'const value_type&' {aka 'const std::pair<int, int>&'}
1187 | push_back(const value_type& __x)
| ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, int>]'
1203 | push_back(value_type&& __x)
| ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1203:30: note: no known conversion for argument 1 from 'int' to 'std::vector<std::pair<int, int> >::value_type&&' {aka 'std::pair<int, int>&&'}
1203 | push_back(value_type&& __x)
| ~~~~~~~~~~~~~^~~
colors.cpp: In member function 'void sgt::go(int)':
colors.cpp:151:13: warning: unused variable 'x' [-Wunused-variable]
151 | for(auto&x:t[v]) dsu.roll();
| ^
colors.cpp: In function 'void solve()':
colors.cpp:204:9: warning: unused variable 'v' [-Wunused-variable]
204 | int v = e.s, j = e.s;
| ^
colors.cpp:213:9: warning: unused variable 'v' [-Wunused-variable]
213 | int v = e.s, j = e.s;
| ^
