oj.uz

Submission #60413

# Submission time Handle Problem Language Result Execution time Memory
60413 2018-07-24T06:49:42 Z 노영훈(#1742) Long Mansion (JOI17_long_mansion) C++11
10 / 100
 3000 ms 23744 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=500010, inf=2e9;

int n, q;
vector<int> A[MX];
int C[MX];
int L[MX], R[MX];

void solve(int v){
    bool key[MX]={};
    for(int x:A[v]) key[x]=true;
    L[v]=R[v]=v;
    while( (L[v]>1&&key[C[L[v]-1]]) || (R[v]<n && key[C[R[v]]])){
        if(L[v]>1 && key[C[L[v]-1]]){
            L[v]--;
            for(int x:A[L[v]]) key[x]=true;
        }
        if(R[v]<n && key[C[R[v]]]){
            R[v]++;
            for(int x:A[R[v]]) key[x]=true;
        }
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for(int i=1; i<n; i++) cin>>C[i];
    for(int i=1; i<=n; i++){
        int b; cin>>b;
        for(int j=1, x; j<=b; j++){ cin>>x, A[i].push_back(x); }
    }
    for(int i=1; i<=n; i++){
        solve(i);
    }
    cin>>q;
    for(int i=1; i<=q; i++){
        int s,e; cin>>s>>e;
        if(L[s]<=e && e<=R[s]) cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 12804 KB Output is correct
2 Correct 121 ms 12968 KB Output is correct
3 Correct 231 ms 13160 KB Output is correct
4 Correct 82 ms 13160 KB Output is correct
5 Correct 104 ms 13256 KB Output is correct
6 Correct 75 ms 13324 KB Output is correct
7 Correct 80 ms 13416 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 12804 KB Output is correct
2 Correct 121 ms 12968 KB Output is correct
3 Correct 231 ms 13160 KB Output is correct
4 Correct 82 ms 13160 KB Output is correct
5 Correct 104 ms 13256 KB Output is correct
6 Correct 75 ms 13324 KB Output is correct
7 Correct 80 ms 13416 KB Output is correct
8 Correct 230 ms 17844 KB Output is correct
9 Correct 211 ms 18144 KB Output is correct
10 Correct 267 ms 18812 KB Output is correct
11 Correct 351 ms 19120 KB Output is correct
12 Correct 169 ms 20964 KB Output is correct
13 Correct 260 ms 21004 KB Output is correct
14 Correct 206 ms 21004 KB Output is correct
15 Correct 198 ms 21044 KB Output is correct
16 Correct 234 ms 21176 KB Output is correct
17 Correct 206 ms 21176 KB Output is correct
18 Correct 235 ms 21176 KB Output is correct
19 Correct 195 ms 21176 KB Output is correct
20 Correct 266 ms 21176 KB Output is correct
21 Correct 301 ms 21256 KB Output is correct
22 Correct 229 ms 21256 KB Output is correct
23 Correct 229 ms 21256 KB Output is correct
24 Correct 220 ms 21256 KB Output is correct
25 Correct 215 ms 21256 KB Output is correct
26 Correct 205 ms 21256 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3045 ms 23744 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 12804 KB Output is correct
2 Correct 121 ms 12968 KB Output is correct
3 Correct 231 ms 13160 KB Output is correct
4 Correct 82 ms 13160 KB Output is correct
5 Correct 104 ms 13256 KB Output is correct
6 Correct 75 ms 13324 KB Output is correct
7 Correct 80 ms 13416 KB Output is correct
8 Correct 230 ms 17844 KB Output is correct
9 Correct 211 ms 18144 KB Output is correct
10 Correct 267 ms 18812 KB Output is correct
11 Correct 351 ms 19120 KB Output is correct
12 Correct 169 ms 20964 KB Output is correct
13 Correct 260 ms 21004 KB Output is correct
14 Correct 206 ms 21004 KB Output is correct
15 Correct 198 ms 21044 KB Output is correct
16 Correct 234 ms 21176 KB Output is correct
17 Correct 206 ms 21176 KB Output is correct
18 Correct 235 ms 21176 KB Output is correct
19 Correct 195 ms 21176 KB Output is correct
20 Correct 266 ms 21176 KB Output is correct
21 Correct 301 ms 21256 KB Output is correct
22 Correct 229 ms 21256 KB Output is correct
23 Correct 229 ms 21256 KB Output is correct
24 Correct 220 ms 21256 KB Output is correct
25 Correct 215 ms 21256 KB Output is correct
26 Correct 205 ms 21256 KB Output is correct
27 Execution timed out 3045 ms 23744 KB Time limit exceeded
28 Halted 0 ms 0 KB -