Submission #1292072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292072		qmdz1908	Long Mansion (JOI17_long_mansion)	C++17	10 / 100	3095 ms	37732 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;
#define pii pair <int, int>
#define fi first
#define se second
const int maxn = 5e5 + 5, mod = 1e9 + 7;
int n, c[maxn];
vector <int> a[maxn];
int mn, mx, has[maxn], vis[maxn];
vector <pii> que[maxn];
bool ans[maxn];
void dfs (int u, int i) {
    vis[u] = i;
    for (int x : a[u]) has[x] = i;
    mn = min (mn, u);
    mx = max (mx, u);
    if (mn > 1 && has[c[mn - 1]] == i) dfs (mn - 1, i);
    if (mx < n && has[c[mx]] == i) dfs (mx + 1, i);
}
void solve () {
    cin >> n;
    for (int i = 1; i < n; i++)
        cin >> c[i];
    for (int i = 1, m; i <= n; i++) {
        cin >> m;
        for (int j = 1, x; j <= m; j++) {
            cin >> x;
            a[i].push_back (x);
        }
    }
    int q;
    cin >> q;
    for (int i = 1, x, y; i <= q; i++) {
        cin >> x >> y;
        que[x].push_back ({y, i});
    }
    for (int i = 1; i <= n; i++) {
        for (int x : a[i]) has[x] = i;
        mn = mx = i;
        dfs (i, i);
        for (auto [y, id] : que[i])
            ans[id] = (vis[y] == i);
    }
    for (int i = 1; i <= q; i++) {
        if (ans[i]) cout << "YES\n";
        else cout << "NO\n";
    }
}
signed main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen ("code.inp", "r")) {
        freopen ("code.inp", "r", stdin);
        freopen ("code.out", "w", stdout);
    }
    int tc = 1;
//    cin >> tc;
    while (tc--) solve ();
}

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:54:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen ("code.inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
long_mansion.cpp:55:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         freopen ("code.out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 15
• Subtask 4: 0 / 75