Comparar texto

Encontre a diferença entre dois arquivos de texto

Editor live

Recolher inalteradas

Sem quebra de linha

Layout

Nível de detalhe

Realce de sintaxe

Diffchecker Desktop A maneira mais segura de usar o Diffchecker. Obtenha o aplicativo Diffchecker Desktop: seus diffs nunca saem do seu computador!Obter Desktop

Untitled diff

Criado há 10 anosO diff nunca expira

12 remoções

Linhas
Total
Removido

Caracteres
Total
Removido

Para continuar usando este recurso, atualize para Diffchecker Pro Ver preços

136 linhas

8 adições

Linhas
Total
Adicionado

Caracteres
Total
Adicionado

Para continuar usando este recurso, atualize para Diffchecker Pro Ver preços

128 linhas

#include <bits/stdc++.h>

using namespace std;

#define error(args...) { vector<string> _v = split(#args, ','); err(_v.begin(), args); }

vector<string> split(const string& s, char c) { vector<string> v; stringstream ss(s); string x; while (getline(ss, x, c)) v.push_back(move(x)); return v; }

void err(vector<string>::iterator it) {}

template<typename T, typename... Args> void err(vector<string>::iterator it, T a, Args... args) { cerr << it->substr((*it)[0] == ' ', it->length()) << " = " << a << '\n'; err(++it, args...); }

#define MAXN 100013

#define MAXM 100013

#define MAXC 100013

#define MAXSQRT 320

int N, M;

int C[MAXN];

vector<int> adj[MAXN];

int preorder[MAXN]; // where a node appears in preorder

int ID[MAXN]; // real value of a preorder index

int endofsubtree[MAXN]; // last element in preorder of subtree of this node

int t = 0;

int BL[MAXN];

struct query {

int id, b, e, k;

bool operator<(query other) {

return BL[b] == BL[other.b] ? e < other.e : BL[b] < BL[other.b];

}

} Q[MAXM];

int VAL[MAXN]; // mo stuff

bool VIS[MAXN];

int ANS[MAXM];

struct fenwick {

int ar[MAXC] = {0};

int query(int idx) {

int ans = 0;

for (int i = idx + 1; i > 0; i -= i & -i) {

ans += ar[i];

}

return ans;

}

void update(int idx, int x) {

for (int i = idx + 1; i < MAXC; i += i & -i) {

ar[i] += x;

}

} F;

void dfs(int n, int prev=-1) {

preorder[n] = t++;

ID[preorder[n]] = n;

for (int x : adj[n]) {

if (x != prev) {

dfs(x, n);

}

endofsubtree[n] = t - 1;

}

inline void check(int x) {

inline void check(int x, int p) {

int prev = VAL[C[x]];

F.update(VAL[C[x]], -1);

if (VIS[x]) {

VAL[C[x]] += p;

VAL[C[x]]--;

}

else {

VAL[C[x]]++;

}

VIS[x] ^= 1;

F.update(prev, -1);

F.update(VAL[C[x]], 1);

}

void compute() {

int curB = Q[0].b, curE = Q[0].b - 1;

for (int i = 0; i < M; i++) {

query q = Q[i];

// error(q.id, q.b, q.e);

while (curB > q.b) check(ID[--curB]);

while (curB > q.b) check(ID[--curB], 1);

while (curB < q.b) check(ID[curB++]);

while (curB < q.b) check(ID[curB++], -1);

while (curE > q.e) check(ID[curE--]);

while (curE > q.e) check(ID[curE--], -1);

while (curE < q.e) check(ID[++curE]);

while (curE < q.e) check(ID[++curE], 1);

ANS[q.id] = F.query(MAXC - 1) - F.query(q.k - 1);

}

int main() {

ios_base::sync_with_stdio(false);

cin.tie(0);

// freopen("input.txt", "r", stdin);

// freopen("output.txt", "w", stdout);

cin >> N >> M;

for (int i = 0; i < N; i++) {

cin >> C[i];

}

// okee read in the edges

for (int i = 0; i < N - 1; i++) {

int a, b;

cin >> a >> b;

a--; b--;

adj[a].push_back(b);

adj[b].push_back(a);

}

dfs(0);

int size = sqrt(N);

for (int i = 0; i < N; i++) {

BL[i] = i / size;

}

for (int i = 0; i < M; i++) {

int v, k;

cin >> v >> k; v--;

Q[i].id = i;

Q[i].b = preorder[v];

Q[i].e = endofsubtree[v];

Q[i].k = k;

}

sort(Q, Q + M);

compute();

for (int i = 0; i < M; i++) {

cout << ANS[i] << '\n';

}

cout.flush();

return 0;

}

Diferenças salvas

Texto original

Abrir arquivo

#include <bits/stdc++.h>
using namespace std;

#define error(args...) { vector<string> _v = split(#args, ','); err(_v.begin(), args); }
vector<string> split(const string& s, char c) { vector<string> v; stringstream ss(s); string x; while (getline(ss, x, c)) v.push_back(move(x)); return v; }
void err(vector<string>::iterator it) {}
template<typename T, typename... Args> void err(vector<string>::iterator it, T a, Args... args) { cerr << it->substr((*it)[0] == ' ', it->length()) << " = " << a << '\n'; err(++it, args...); }

#define MAXN 100013
#define MAXM 100013
#define MAXC 100013
#define MAXSQRT 320

int N, M;
int C[MAXN];
vector<int> adj[MAXN];
int preorder[MAXN]; // where a node appears in preorder
int ID[MAXN]; // real value of a preorder index
int endofsubtree[MAXN]; // last element in preorder of subtree of this node
int t = 0;
int BL[MAXN];

struct query {
	int id, b, e, k;
	bool operator<(query other) {
		return BL[b] == BL[other.b] ? e < other.e : BL[b] < BL[other.b];
	}
} Q[MAXM];
int VAL[MAXN]; // mo stuff
bool VIS[MAXN];
int ANS[MAXM];

struct fenwick {
	int ar[MAXC] = {0};
	int query(int idx) {
		int ans = 0;
		for (int i = idx + 1; i > 0; i -= i & -i) {
			ans += ar[i];
		}
		return ans;
	}
	void update(int idx, int x) {
		for (int i = idx + 1; i < MAXC; i += i & -i) {
			ar[i] += x;
		}
	}
} F;

void dfs(int n, int prev=-1) {
	preorder[n] = t++;
	ID[preorder[n]] = n;

for (int x : adj[n]) {
		if (x != prev) {
			dfs(x, n);
		}
	}

endofsubtree[n] = t - 1;
}

inline void check(int x) {
	int prev = VAL[C[x]];
	if (VIS[x]) {
		VAL[C[x]]--;
	}
	else {
		VAL[C[x]]++;
	}
	VIS[x] ^= 1;
	F.update(prev, -1);
	F.update(VAL[C[x]], 1);
}

void compute() {
	int curB = Q[0].b, curE = Q[0].b - 1;
	for (int i = 0; i < M; i++) {
		query q = Q[i];
		// error(q.id, q.b, q.e);

while (curB > q.b) check(ID[--curB]);
		while (curB < q.b) check(ID[curB++]);
		while (curE > q.e) check(ID[curE--]);
		while (curE < q.e) check(ID[++curE]);

ANS[q.id] = F.query(MAXC - 1) - F.query(q.k - 1);
	}
}

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

// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);

cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> C[i];
	}

// okee read in the edges
	for (int i = 0; i < N - 1; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

dfs(0);

int size = sqrt(N);
	for (int i = 0; i < N; i++) {
		BL[i] = i / size;
	}

for (int i = 0; i < M; i++) {
		int v, k;
		cin >> v >> k; v--;
		Q[i].id = i;
		Q[i].b = preorder[v];
		Q[i].e = endofsubtree[v];
		Q[i].k = k;
	}

sort(Q, Q + M);
	compute();
	for (int i = 0; i < M; i++) {
		cout << ANS[i] << '\n';
	}

cout.flush();
	return 0;
}

Texto alterado

Abrir arquivo

#include <bits/stdc++.h>
using namespace std;

#define MAXN 100013
#define MAXM 100013
#define MAXC 100013
#define MAXSQRT 320

struct query {
	int id, b, e, k;
	bool operator<(query other) {
		return BL[b] == BL[other.b] ? e < other.e : BL[b] < BL[other.b];
	}
} Q[MAXM];
int VAL[MAXN]; // mo stuff
int ANS[MAXM];

void dfs(int n, int prev=-1) {
	preorder[n] = t++;
	ID[preorder[n]] = n;

for (int x : adj[n]) {
		if (x != prev) {
			dfs(x, n);
		}
	}

endofsubtree[n] = t - 1;
}

inline void check(int x, int p) {
	F.update(VAL[C[x]], -1);
	VAL[C[x]] += p;
	F.update(VAL[C[x]], 1);
}

void compute() {
	int curB = Q[0].b, curE = Q[0].b - 1;
	for (int i = 0; i < M; i++) {
		query q = Q[i];
		// error(q.id, q.b, q.e);

while (curB > q.b) check(ID[--curB], 1);
		while (curB < q.b) check(ID[curB++], -1);
		while (curE > q.e) check(ID[curE--], -1);
		while (curE < q.e) check(ID[++curE], 1);

ANS[q.id] = F.query(MAXC - 1) - F.query(q.k - 1);
	}
}

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

// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);

cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> C[i];
	}

// okee read in the edges
	for (int i = 0; i < N - 1; i++) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

dfs(0);

int size = sqrt(N);
	for (int i = 0; i < N; i++) {
		BL[i] = i / size;
	}

for (int i = 0; i < M; i++) {
		int v, k;
		cin >> v >> k; v--;
		Q[i].id = i;
		Q[i].b = preorder[v];
		Q[i].e = endofsubtree[v];
		Q[i].k = k;
	}

sort(Q, Q + M);
	compute();
	for (int i = 0; i < M; i++) {
		cout << ANS[i] << '\n';
	}

cout.flush();
	return 0;
}