oj.uz

Submission #347419

# Submission time Handle Problem Language Result Execution time Memory
347419 2021-01-13T02:24:07 Z guka415 Long Mansion (JOI17_long_mansion) C++14
25 / 100
 3000 ms 138476 KB 
#define _CRT_SECURE_NO_WARNINGS
#define fast ios::sync_with_stdio(false); cin.tie(0)
#define foru(i, k, n) for (int i = k; i < n; i++)
#define ford(i, k, n) for (int i = k; i >= n; i--)
#define pb push_back
#define ff first
#define ss second
 
#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
#include <queue>
#include <unordered_set>
#include <set>
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int sz = 5e5 + 5;
int n, m, c[sz], nc[sz];
vector<int> a[sz], na[sz], adj[sz];
int lfinal[sz], rfinal[sz], closestL[sz], closestR[sz], lmn[sz], rmx[sz];
short connectedTo[sz];
vector<pii> comps;
vector<int> top;
vector<int> st[sz];
 
void input() {
	scanf("%d", &n);
	foru(i, 0, n - 1) {
		scanf("%d", &c[i]); c[i]--;
	}
	foru(i, 0, n) {
		int tmp, xx;
		scanf("%d", &tmp);
		while (tmp--) {
			scanf("%d", &xx);
			a[i].pb(--xx);
		}
	}
}
 
void computeConnectedTo() {
	foru(i, 0, n) {
      	st[i].push_back(-1);
		bool found = 0;
		if (i != 0) {
			for (int x : a[i]) {
				if (x == c[i - 1]) {
					connectedTo[i] = -1;
					found = 1;
					break;
				}
			}
			if (found)continue;
		}
		if (i != n - 1) {
			for (int x : a[i]) {
				if (x == c[i]) {
					connectedTo[i] = 1;
					found = 1;
					break;
				}
			}
			if (found)continue;
		}
	}
}
 
void computeComps() {
	int prvStart = 0;
	foru(i, 0, n) {
		if (i == n - 1 || connectedTo[i] != 1 || connectedTo[i + 1] != -1) {
			comps.pb({ prvStart,i });
			prvStart = i + 1;
		}
	}
	m = comps.size();
	unordered_set<int> mem;
	foru(i, 0, m) {
		mem.clear();
		foru(j, comps[i].ff, comps[i].ss + 1) {
			for (int x : a[j])mem.insert(x);
		}
		for (int x : mem) {
			na[i].pb(x);
			st[x].push_back(i);
		}
		if (connectedTo[comps[i].ff] == -1)adj[i - 1].pb(i);
		if (connectedTo[comps[i].ss] == 1)adj[i + 1].pb(i);
		if (i != m - 1)nc[i] = c[comps[i].ss];
		lfinal[i] = rfinal[i] = i;
	}
}
 
void topoSort() {
	vector<int> indeg(m, 0);
	foru(i, 0, m) {
		for (int x : adj[i])indeg[x]++;
	}
	queue<int> q;
	foru(i, 0, m) {
		if (indeg[i] == 0)q.push(i);
	}
	while (!q.empty()) {
		int x = q.front(); q.pop();
		top.pb(x);
		for (int y : adj[x]) {
			indeg[y]--;
			if (indeg[y] == 0)q.push(y);
		}
	}
}
 
void computeClosest() {
	for (int i = 0; i < n; i++) {
		st[i].push_back(m + 1);
	}
	for (int i = 0; i < m - 1; i++) {
		auto it = upper_bound(st[nc[i]].begin(),st[nc[i]].end(),i);
		closestR[i] = (*it);
		--it;
		closestL[i] = (*it);
	}
}
 
void computeRanges() {
	int src;
	foru(i, 0, m) {
		src = top[i];
		if (connectedTo[comps[src].ff] == 0 && connectedTo[comps[src].ss] == 0)continue;
		else if (connectedTo[comps[src].ss] == 1) {
			if (lfinal[src + 1] <= src) {
				lfinal[src] = lfinal[src + 1];
				rfinal[src] = rfinal[src + 1];
				continue;
			}
			lfinal[src] = min(lfinal[src], lfinal[src + 1]);
			rfinal[src] = max(rfinal[src], rfinal[src + 1]);
		}
		else if (connectedTo[comps[src].ff] == -1) {
			if (rfinal[src - 1] >= src) {
				lfinal[src] = lfinal[src - 1];
				rfinal[src] = rfinal[src - 1];
				continue;
			}
			lfinal[src] = min(lfinal[src], lfinal[src - 1]);
			rfinal[src] = max(rfinal[src], rfinal[src - 1]);
		}
		while (true) {
			if (rfinal[src] != m - 1 && closestL[rfinal[src]] >= lfinal[src]) rfinal[src]++;
			else if (lfinal[src] != 0 && closestR[lfinal[src] - 1] <= rfinal[src]) lfinal[src]--;
			else break;
		}
	}
}
 
void computeFinal() {
	foru(i, 0, m) {
		foru(j, comps[i].ff, comps[i].ss + 1) {
			lmn[j] = comps[lfinal[i]].ff;
			rmx[j] = comps[rfinal[i]].ss;
		}
	}
}
 
int main() {
	fast;
	input();
	computeConnectedTo();
	computeComps();
	topoSort();
	computeClosest();
	computeRanges();
	computeFinal();
	int q, x, y;
	scanf("%d", &q);
	while (q--) {
		scanf("%d %d", &x, &y);
		x--; y--;
		if (y >= lmn[x] && y <= rmx[x])printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

Compilation message

long_mansion.cpp: In function 'void input()':
long_mansion.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
long_mansion.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |   scanf("%d", &c[i]); c[i]--;
      |   ~~~~~^~~~~~~~~~~~~
long_mansion.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |   scanf("%d", &tmp);
      |   ~~~~~^~~~~~~~~~~~
long_mansion.cpp:41:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |    scanf("%d", &xx);
      |    ~~~~~^~~~~~~~~~~
long_mansion.cpp: In function 'int main()':
long_mansion.cpp:181:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  181 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
long_mansion.cpp:183:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  183 |   scanf("%d %d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47852 KB Output is correct
2 Correct 33 ms 47980 KB Output is correct
3 Correct 39 ms 48236 KB Output is correct
4 Correct 32 ms 47852 KB Output is correct
5 Correct 32 ms 47852 KB Output is correct
6 Correct 32 ms 47852 KB Output is correct
7 Correct 32 ms 47724 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47852 KB Output is correct
2 Correct 33 ms 47980 KB Output is correct
3 Correct 39 ms 48236 KB Output is correct
4 Correct 32 ms 47852 KB Output is correct
5 Correct 32 ms 47852 KB Output is correct
6 Correct 32 ms 47852 KB Output is correct
7 Correct 32 ms 47724 KB Output is correct
8 Correct 171 ms 53628 KB Output is correct
9 Correct 174 ms 53740 KB Output is correct
10 Correct 173 ms 54380 KB Output is correct
11 Correct 177 ms 54764 KB Output is correct
12 Correct 170 ms 53100 KB Output is correct
13 Correct 171 ms 53868 KB Output is correct
14 Correct 169 ms 53868 KB Output is correct
15 Correct 166 ms 53996 KB Output is correct
16 Correct 167 ms 53868 KB Output is correct
17 Correct 171 ms 53868 KB Output is correct
18 Correct 168 ms 53868 KB Output is correct
19 Correct 168 ms 53868 KB Output is correct
20 Correct 170 ms 53868 KB Output is correct
21 Correct 167 ms 53808 KB Output is correct
22 Correct 166 ms 53868 KB Output is correct
23 Correct 168 ms 53612 KB Output is correct
24 Correct 167 ms 53612 KB Output is correct
25 Correct 176 ms 53612 KB Output is correct
26 Correct 168 ms 53728 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 956 ms 75748 KB Output is correct
2 Correct 1593 ms 75232 KB Output is correct
3 Correct 2365 ms 74704 KB Output is correct
4 Correct 1154 ms 75496 KB Output is correct
5 Correct 1278 ms 75364 KB Output is correct
6 Correct 937 ms 72800 KB Output is correct
7 Correct 762 ms 73696 KB Output is correct
8 Correct 597 ms 73896 KB Output is correct
9 Correct 520 ms 73952 KB Output is correct
10 Correct 364 ms 74080 KB Output is correct
11 Correct 362 ms 74080 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47852 KB Output is correct
2 Correct 33 ms 47980 KB Output is correct
3 Correct 39 ms 48236 KB Output is correct
4 Correct 32 ms 47852 KB Output is correct
5 Correct 32 ms 47852 KB Output is correct
6 Correct 32 ms 47852 KB Output is correct
7 Correct 32 ms 47724 KB Output is correct
8 Correct 171 ms 53628 KB Output is correct
9 Correct 174 ms 53740 KB Output is correct
10 Correct 173 ms 54380 KB Output is correct
11 Correct 177 ms 54764 KB Output is correct
12 Correct 170 ms 53100 KB Output is correct
13 Correct 171 ms 53868 KB Output is correct
14 Correct 169 ms 53868 KB Output is correct
15 Correct 166 ms 53996 KB Output is correct
16 Correct 167 ms 53868 KB Output is correct
17 Correct 171 ms 53868 KB Output is correct
18 Correct 168 ms 53868 KB Output is correct
19 Correct 168 ms 53868 KB Output is correct
20 Correct 170 ms 53868 KB Output is correct
21 Correct 167 ms 53808 KB Output is correct
22 Correct 166 ms 53868 KB Output is correct
23 Correct 168 ms 53612 KB Output is correct
24 Correct 167 ms 53612 KB Output is correct
25 Correct 176 ms 53612 KB Output is correct
26 Correct 168 ms 53728 KB Output is correct
27 Correct 956 ms 75748 KB Output is correct
28 Correct 1593 ms 75232 KB Output is correct
29 Correct 2365 ms 74704 KB Output is correct
30 Correct 1154 ms 75496 KB Output is correct
31 Correct 1278 ms 75364 KB Output is correct
32 Correct 937 ms 72800 KB Output is correct
33 Correct 762 ms 73696 KB Output is correct
34 Correct 597 ms 73896 KB Output is correct
35 Correct 520 ms 73952 KB Output is correct
36 Correct 364 ms 74080 KB Output is correct
37 Correct 362 ms 74080 KB Output is correct
38 Correct 546 ms 123744 KB Output is correct
39 Correct 573 ms 138476 KB Output is correct
40 Correct 476 ms 108508 KB Output is correct
41 Execution timed out 3094 ms 125656 KB Time limit exceeded
42 Halted 0 ms 0 KB -