Submission #262763

#TimeUsernameProblemLanguageResultExecution timeMemory
262763dantoh000Colors (RMI18_colors)C++14
78 / 100
893 ms106736 KiB
#include <bits/stdc++.h> #define fi first #define se second using namespace std; typedef pair<int,int> ii; int n,m; int A[150005]; int B[150005]; int U[150005]; int V[150005]; int has[150005]; vector<int> source[150005]; vector<int> sink[150005]; int ans = 0; struct UFDS{ vector<ii> op; int p[150005]; int sz[150005]; void init(int n){ for (int i = 1 ; i <= n; i++){ p[i] = i; sz[i] = 1; } } int find(int x){ return x == p[x] ? x : find(p[x]); } void un(int x, int y){ x = find(x), y = find(y); if (x == y) return; if (sz[x] < sz[y]) swap(x,y); p[y] = x; sz[x] += sz[y]; op.push_back({x,y}); } void roll(int SZ){ int x,y; while (op.size() > SZ){ tie(x,y) = op.back(); op.pop_back(); sz[x] -= sz[y]; p[y] = y; } } } ufds; struct node{ int s,e,m; vector<ii> V; node *l, *r; node (int _s, int _e): s(_s), e(_e){ m = (s+e)/2; if (s != e){ l = new node(s,m); r = new node(m+1,e); } } void up(int qs ,int qe, ii v){ if (qs == s && qe == e){ V.push_back(v); return; } if (qs > m) r->up(qs,qe,v); else if (qe<=m) l->up(qs,qe,v); else l->up(qs,m,v), r->up(m+1,qe,v); } void dfs(){ int oldsz = ufds.op.size(); for (auto x : V){ ufds.un(x.fi,x.se); } if (s == e){ for (auto x : source[s]){ has[ufds.find(x)] = 1; } for (auto x : sink[s]){ if (!has[ufds.find(x)]) ans = 0; } for (auto x : source[s]){ has[ufds.find(x)] = 0; } } else{ l->dfs(); r->dfs(); } ufds.roll(oldsz); } } *root; int main(){ int TC; scanf("%d",&TC); while (TC--){ ans = 1; scanf("%d%d",&n,&m); root = new node(1,n); ufds.init(n); for (int i = 1; i <= n; i++){ source[i].clear(); sink[i].clear(); } for (int i = 1; i <= n; i++) { scanf("%d",&A[i]); source[A[i]].push_back(i); } for (int i = 1; i <= n; i++) { scanf("%d",&B[i]); sink[B[i]].push_back(i); } for (int i = 1; i <= m; i++) { scanf("%d%d",&U[i],&V[i]); int L = max(B[U[i]],B[V[i]]); int R = min(A[U[i]],A[V[i]]); if (L > R) continue; root->up(L,R,ii(U[i],V[i])); } root->dfs(); printf("%d\n",ans); } }

Compilation message (stderr)

colors.cpp: In member function 'void UFDS::roll(int)':
colors.cpp:38:26: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |         while (op.size() > SZ){
      |                ~~~~~~~~~~^~~~
colors.cpp: In function 'int main()':
colors.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |     scanf("%d",&TC);
      |     ~~~~~^~~~~~~~~~
colors.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |         scanf("%d%d",&n,&m);
      |         ~~~~~^~~~~~~~~~~~~~
colors.cpp:101:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  101 |             scanf("%d",&A[i]);
      |             ~~~~~^~~~~~~~~~~~
colors.cpp:105:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  105 |             scanf("%d",&B[i]);
      |             ~~~~~^~~~~~~~~~~~
colors.cpp:109:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  109 |             scanf("%d%d",&U[i],&V[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...