oj.uz

Submission #482309

# Submission time Handle Problem Language Result Execution time Memory
482309 2021-10-24T04:41:19 Z MilosMilutinovic Colors (RMI18_colors) C++14
100 / 100
 647 ms 185804 KB 
#include <bits/stdc++.h>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define pb push_back
#define pii pair<int,int>
#define xx first
#define yy second

using namespace std;

int n,m;
int a[150005];
int b[150005];

vector<int> x[150005];
vector<int> y[150005];

vector<pii> edges;

int dsu[150005];
int sajz[150005];

struct op{
	int a,b,sza,szb;
};
stack<op> stk;

int finddsu(int x){
	if(dsu[x] == x)return x;
	return finddsu(dsu[x]);
}
void spoji(int a, int b){
	a = finddsu(a);
	b = finddsu(b);
	if(sajz[a] < sajz[b])swap(a, b);
	stk.push({a, b, sajz[a], sajz[b]});
	if(a == b)return;
	dsu[b] = dsu[a];
	sajz[a] += sajz[b];
}
void rollback(){
	op lst = stk.top();
	stk.pop();
	dsu[lst.a] = lst.a;
	dsu[lst.b] = lst.b;
	sajz[lst.a] = lst.sza;
	sajz[lst.b] = lst.szb;
}


vector<pii> st[5000005];

void klir(){
	edges.clear();
	ff(i,1,n){
//		graf[i].clear();
		x[i].clear();
		y[i].clear();
	}
	ff(i,1,4*n)st[i].clear();
}

void update(int node, int l, int r, int ll, int rr, pii edge){
	if(l > r || l > rr || r < ll)return;
	if(ll <= l && r <= rr){
		st[node].pb(edge);
		return;
	}
	int mid = (l + r) / 2;
	update(node * 2, l, mid, ll, rr, edge);
	update(node * 2 + 1, mid + 1, r, ll, rr, edge);
}

bool ok;

void dfs(int node, int l, int r){
	for(auto c : st[node])spoji(c.xx, c.yy);
	if(l == r){
		map<int, bool> mapa;
		for(auto c : x[l])mapa[finddsu(c)] = true;
		for(auto c : y[l]){
			if(!mapa[finddsu(c)])ok = false;
		}
	}
	else{
		int mid = (l + r) / 2;
		dfs(node * 2, l, mid);
		dfs(node * 2 + 1, mid + 1, r);
	}
	for(auto c : st[node])rollback();
}



void solve(){
	cin >> n >> m;
	ff(i,1,n)dsu[i] = i, sajz[i] = 1;
	ff(i,1,n)cin >> a[i];
	ff(i,1,n)cin >> b[i];
	ff(i,1,m){
		int u,v;
		cin >> u >> v;
//		graf[u].pb(v);
//		graf[v].pb(u);
		edges.pb({u,v});
	}
	ff(i,1,n)x[a[i]].pb(i);
	ff(i,1,n)y[b[i]].pb(i);
	ff(i,1,n){
		if(a[i] < b[i]){
			klir();
			cout << "0\n";
			return;
		}
	}

	for(auto x:edges){
		int u = x.xx;
		int v = x.yy;
		int A = max(b[u], b[v]);
		int B = min(a[u], a[v]);
		if(A <= B)update(1, 1, n, A, B, x); // mogu da koristim granu!!!
	}
	ok = true;
	dfs(1, 1, n);
	cout << ok << "\n";
	klir();
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int t;
	cin >> t;
	while(t--)solve();

	return 0;
}

Compilation message

colors.cpp: In function 'void klir()':
colors.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
colors.cpp:55:2: note: in expansion of macro 'ff'
   55 |  ff(i,1,n){
      |  ^~
colors.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
colors.cpp:60:2: note: in expansion of macro 'ff'
   60 |  ff(i,1,4*n)st[i].clear();
      |  ^~
colors.cpp: In function 'void dfs(int, int, int)':
colors.cpp:90:11: warning: variable 'c' set but not used [-Wunused-but-set-variable]
   90 |  for(auto c : st[node])rollback();
      |           ^
colors.cpp: In function 'void solve()':
colors.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
colors.cpp:97:2: note: in expansion of macro 'ff'
   97 |  ff(i,1,n)dsu[i] = i, sajz[i] = 1;
      |  ^~
colors.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
colors.cpp:98:2: note: in expansion of macro 'ff'
   98 |  ff(i,1,n)cin >> a[i];
      |  ^~
colors.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
colors.cpp:99:2: note: in expansion of macro 'ff'
   99 |  ff(i,1,n)cin >> b[i];
      |  ^~
colors.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
colors.cpp:100:2: note: in expansion of macro 'ff'
  100 |  ff(i,1,m){
      |  ^~
colors.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
colors.cpp:107:2: note: in expansion of macro 'ff'
  107 |  ff(i,1,n)x[a[i]].pb(i);
      |  ^~
colors.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
colors.cpp:108:2: note: in expansion of macro 'ff'
  108 |  ff(i,1,n)y[b[i]].pb(i);
      |  ^~
colors.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
colors.cpp:109:2: note: in expansion of macro 'ff'
  109 |  ff(i,1,n){
      |  ^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 126232 KB Output is correct
2 Correct 91 ms 125372 KB Output is correct
3 Correct 70 ms 125188 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 126696 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 126228 KB Output is correct
2 Correct 83 ms 125256 KB Output is correct
3 Correct 65 ms 124996 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 126228 KB Output is correct
2 Correct 83 ms 125256 KB Output is correct
3 Correct 65 ms 124996 KB Output is correct
4 Correct 184 ms 127884 KB Output is correct
5 Correct 415 ms 147076 KB Output is correct
6 Correct 630 ms 168560 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 126232 KB Output is correct
2 Correct 91 ms 125372 KB Output is correct
3 Correct 70 ms 125188 KB Output is correct
4 Correct 130 ms 126228 KB Output is correct
5 Correct 83 ms 125256 KB Output is correct
6 Correct 65 ms 124996 KB Output is correct
7 Correct 118 ms 126272 KB Output is correct
8 Correct 83 ms 125328 KB Output is correct
9 Correct 64 ms 125072 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 128060 KB Output is correct
2 Correct 410 ms 147900 KB Output is correct
3 Correct 429 ms 158676 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 125636 KB Output is correct
2 Correct 70 ms 125536 KB Output is correct
3 Correct 65 ms 125016 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 126232 KB Output is correct
2 Correct 91 ms 125372 KB Output is correct
3 Correct 70 ms 125188 KB Output is correct
4 Correct 117 ms 126696 KB Output is correct
5 Correct 130 ms 126228 KB Output is correct
6 Correct 83 ms 125256 KB Output is correct
7 Correct 65 ms 124996 KB Output is correct
8 Correct 184 ms 127884 KB Output is correct
9 Correct 415 ms 147076 KB Output is correct
10 Correct 630 ms 168560 KB Output is correct
11 Correct 118 ms 126272 KB Output is correct
12 Correct 83 ms 125328 KB Output is correct
13 Correct 64 ms 125072 KB Output is correct
14 Correct 186 ms 128060 KB Output is correct
15 Correct 410 ms 147900 KB Output is correct
16 Correct 429 ms 158676 KB Output is correct
17 Correct 86 ms 125636 KB Output is correct
18 Correct 70 ms 125536 KB Output is correct
19 Correct 65 ms 125016 KB Output is correct
20 Correct 139 ms 127484 KB Output is correct
21 Correct 430 ms 151504 KB Output is correct
22 Correct 647 ms 185804 KB Output is correct