Submission #638737

#	Time	Username	Problem	Language	Result	Execution time	Memory
638737		aebov	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	336 ms	64176 KiB

long_mansion

#include<iostream>
#include<algorithm>
#include<time.h>
#include<vector>
#include<stack>
#include<iomanip> 
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<string.h>
#include<climits>
#include<utility>
#define    ull            unsigned long long
#define    mk             make_pair
#define    pb             push_back
#define    ll             long long
#define    endl           '\n'
#define    pii            pair<int,int>
#define	   pcc            pair<char,char>
#define    vi             vector<ll int> 
#define    pll            pair<ll int,ll int>
#define    F              first
#define    S              second
#define    kill_		  cout<<0<<endl,exit(0);
using namespace std;

int n,q,k,x,y;
const int N = 500002;
vector <int> kotagh[N];
int lans[N],rans[N],keys[N];

void reachable__(int x)
{
    bool fl = true;
    while(fl)
	{
        fl = false;
        int tmn;
	tmn = (lans[x] == 1 ? N : *lower_bound( kotagh[keys[lans[x]-1]].begin(), kotagh[keys[lans[x]-1]].end(), lans[x])); 
        if (tmn <= rans[x])
        {
            int tmp = lans[x]--;
            lans[x]  = min(lans[x], lans[ lans[x] ]),rans[x] = max(rans[x] ,rans[ lans[x]]),fl = true;
        }
        else
        {
            int tml = (rans[x] == n ? N : *lower_bound( kotagh[keys[rans[x]]].begin(), kotagh[keys[rans[x]]].end(), lans[x]));
            if (tml <= rans[x])
            {
                rans[x]++;
                reachable__(rans[x]);
                lans[x]  = min(lans[x], lans[ rans[x] ]),rans[x] = max(rans[x] ,rans[ rans[x]]),fl = 1;
            }
        }
    }
}
void input()
{
    cin >> n;
    for (int i = 1; i <= n-1; i++)cin >> keys[i];
    for (int i = 1; i <= n; i++)
    {
        int ted;cin >> ted;
        for (int j = 1; j <= ted; j++){cin >> k;kotagh[k].push_back(i);}
    }
    for (int i = 1; i <= n; i++)
    {
        lans[i] = rans[i] = i;
        kotagh[i].push_back(N);
    }
}
void solve()
{
    for (int i = 1; i <= n; i++)reachable__(i);
    cin >> q;
    while(q--)
    {
       cin >> x >> y;
       cout<<((lans[x] <= y && rans[x] >= y)?"YES\n":"NO\n");
    }
}
void optimize(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
int main(){optimize();input();solve();}

Compilation message (stderr)

long_mansion.cpp: In function 'void reachable__(int)':
long_mansion.cpp:43:17: warning: unused variable 'tmp' [-Wunused-variable]
   43 |             int tmp = lans[x]--;
      |                 ^~~

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