Submission #827379

#	Time	Username	Problem	Language	Result	Execution time	Memory
827379		lovrot	Tourism (JOI23_tourism)	C++17	100 / 100	618 ms	27592 KiB

tourism

#include <bits/stdc++.h>

#define X first
#define Y second
#define pb push_back
#define MP make_pair

using namespace std; 

typedef long long ll; 
typedef pair<int, int> pii; 

int abs(int x) {
	if(x < 0) return -x;
	return x;
}

const int LOG = 17; 
const int OFF = 1 << LOG; 
const int INF = 1e9;

struct intv {
	int l, r, val;
	bool op;
	intv (int l, int r, int val) : l(l), r(r), val(val) { op = 0; }
	intv (int l, int r, int val, int op) : l(l), r(r), val(val), op(op) {}
	bool operator< (intv a) const { return l < a.l || (l == a.l && r < a.r); }
};

int CNT; 
int head[OFF], heav[OFF], pos[OFF], par[OFF], dep[OFF];

vector<int> g[OFF]; 
vector<intv> ups;

int dfs(int u) {
	int siz = 1, maxs = 0, ind = 0;
	for(int v : g[u]) {
		if(v == par[u]) continue; 
		par[v] = u, dep[v] = dep[u] + 1;
		int res = dfs(v); 
		if(res > maxs) maxs = res, ind = v;
		siz += res;
	}
	heav[u] = ind; 
	// printf("%d -> %d\n", u, ind);
	return siz;
} 

void decomp(int u, int h) {
	pos[u] = CNT++, head[u] = h;
	// printf("%d[%d, %d]\n", u, pos[u], head[u]);
	if(heav[u] && u != 1) decomp(heav[u], h); 
	for(int v : g[u]) {
		if(v == par[u] || v == heav[u] && u != 1) continue;
		decomp(v, v);
	}
}

int fen[OFF];
set<intv> s; 

void add(int x, int val) {
	for(x; x < OFF; x += x & -x) fen[x] += val;
}

int sum(int x) {
	int ret = 0; 
	for(x; x; x -= x & -x) ret += fen[x]; 
	return ret;
}

void change(intv i) {
	// if(i.op) printf("%d %d -%d\n", i.l, i.r, i.val);
	// else printf("%d %d %d\n", i.l, i.r, i.val);
	int val = i.r - i.l + 1;
	if(i.op) val = -val;
	add(i.val + 1, val); 
}

void debug() {
	for(auto it : s) {
		printf("[%d, %d (%d)] ", it.l, it.r, it.val);
	}
	printf("\n");
}

//shit
void interval(int l, int r, int val) {
	if(l > r) return;

	ups.clear(); 
	ups.pb(intv(l, r, val)); 
	auto it = prev(s.upper_bound(intv(l, INF, INF)));

	if(it->l < l) ups.pb(intv(it->l, l - 1, it->val)); 
	
	while(it != s.end() && it->l <= r) {
		if(it->r > r) ups.pb(intv(r + 1, it->r, it->val)); 
		auto nit = next(it);
		change(intv(it->l, it->r, it->val, 1));  
		s.erase(it); 
		it = nit;
	}
	for(intv p : ups) {
		s.insert(p);
		change(p);
	}
	//printf("add %d %d %d\n", l, r, val);
	// debug();
}

void update(int u, int v, int val) {
	for(; head[u] != head[v]; v = par[head[v]]) {
		if(dep[head[u]] > dep[head[v]]) swap(u, v); 
		interval(pos[head[v]], pos[v], val); 
	}
	if(dep[u] > dep[v]) swap(u, v);
	interval(pos[u] + 1, pos[v], val); 
}

int n, m, t, ans[OFF]; 
vector<int> c;
vector<pii> q[OFF]; 

int main() {
	scanf("%d%d%d", &n, &m, &t); 
	for(int i = 0; i < n - 1; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		g[a].pb(b); 
		g[b].pb(a); 
	}
	dfs(1); 
	decomp(1, 1); 

	change(intv(1, n - 1, 0));
	s.insert(intv(1, n - 1, 0)); 

	for(int i = 0; i < m; i++) {
		int x;
		scanf("%d", &x); 
		c.pb(x); 
	}

	for(int i = 0; i < t; i++) {
		int l, r;
		scanf("%d%d", &l, &r); 
		q[r].pb({l, i}); 
	}

	for(int i = 1; i <= m; i++) {
		if(i != 1) update(c[i - 2], c[i - 1], i - 1);
		for(pii p : q[i]) ans[p.Y] = sum(p.X);   
	}

	for(int i = 0; i < t; i++) printf("%d\n", n - ans[i]);
	return 0;	
}

Compilation message (stderr)

tourism.cpp: In function 'void decomp(int, int)':
tourism.cpp:55:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   55 |   if(v == par[u] || v == heav[u] && u != 1) continue;
      |                     ~~~~~~~~~~~~~^~~~~~~~~
tourism.cpp: In function 'void add(int, int)':
tourism.cpp:64:6: warning: statement has no effect [-Wunused-value]
   64 |  for(x; x < OFF; x += x & -x) fen[x] += val;
      |      ^
tourism.cpp: In function 'int sum(int)':
tourism.cpp:69:6: warning: statement has no effect [-Wunused-value]
   69 |  for(x; x; x -= x & -x) ret += fen[x];
      |      ^
tourism.cpp: In function 'int main()':
tourism.cpp:127:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |  scanf("%d%d%d", &n, &m, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
tourism.cpp:130:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~
tourism.cpp:142:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |   scanf("%d", &x);
      |   ~~~~~^~~~~~~~~~
tourism.cpp:148:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |   scanf("%d%d", &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 18 / 18
• Subtask 5: 24 / 24
• Subtask 6: 41 / 41