Submission #482309

#	Time	Username	Problem	Language	Result	Execution time	Memory
482309		MilosMilutinovic	Colors (RMI18_colors)	C++14	100 / 100	647 ms	185804 KiB

colors

#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 (stderr)

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 / 15
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 10 / 10
• Subtask 8: 22 / 22