oj.uz

Submission #801450

# Submission time Handle Problem Language Result Execution time Memory
801450 2023-08-02T06:10:23 Z vjudge1 Long Mansion (JOI17_long_mansion) C++14
10 / 100
 3000 ms 79544 KB 
#include<bits/stdc++.h>
using namespace std ;
const int N = (1 << 19), NS = 5e3, NSS = (1 << 17) ;
bool flag, us[NS + 1][NS + 1] ;
int n, q, sm, c[N + 1] ;
vector<int> sg[2 * NSS + 1], sg_b[2 * NSS + 1] ;
vector<int> nul, ks[N + 1] ;
map<int, int> ch, null ;
void bfs(int city)
{
    ch = null ;
    bool abu = 1 ;
    int l = city, r = city ;
    for(int i : ks[city])
        ch[i] = 1 ;
    us[city][city] = 1 ;
    while(abu)
    {
        abu ^= 1 ;
        if(l > 1 && ch[c[l - 1]])
        {
            l-- ;
            for(int i : ks[l])
                ch[i] = 1 ;
            us[city][l] = 1 ;
            abu |= 1 ;
        }
        if(r < n && ch[c[r]])
        {
            abu |= 1 ;
            r++ ;
            for(int i : ks[r])
                ch[i] = 1 ;
            us[city][r] = 1 ;
        }
    }
}
vector<int> mrg(vector<int> a, vector<int> b)
{
    if(!a.size() || !b.size())
    {
        if(a.size())
            return a ;
        else
            return b ;
    }
    int uk1 = 0, uk2 = 0 ;
    vector<int> c ;
    while(uk1 < a.size() || uk2 < b.size())
    {
        int mn = 21 ;
        if(uk1 < a.size())
            mn = min(mn, a[uk1]) ;
        if(uk2 < b.size())
            mn = min(mn, b[uk2]) ;
        if(!c.size() || c.back() != mn)
            c.push_back(mn) ;
        if(uk1 < a.size() && a[uk1] == mn)
            uk1++ ;
        else
            uk2++ ;
    }
    return c ;
}
void build(int l, int r, int v)
{
    if(l == r)
    {
        if(l <= n)
        {
            for(int j : ks[l])
                sg_b[v].push_back(j) ;
        }
        if(l < n)
            sg[v].push_back(c[l]) ;
        return ;
    }
    int mid = (l + r) >> 1 ;
    build(l, mid, v * 2) ;
    build(mid + 1, r, v * 2 + 1) ;
    sg[v] = mrg(sg[v * 2], sg[v * 2 + 1]) ;
    sg_b[v] = mrg(sg_b[v * 2], sg_b[v * 2 + 1]) ;
}
vector<int> get_all(int l, int r, int l1, int r1, int v)
{
    if(l > r1 || r < l1)
        return nul ;
    if(l1 <= l && r <= r1)
        return sg[v] ;
    int mid = (l + r) >> 1 ;
    return mrg(get_all(l, mid, l1, r1, v * 2), get_all(mid + 1, r, l1, r1, v * 2 + 1)) ;
}
vector<int> get_all_b(int l, int r, int l1, int r1, int v)
{
    if(l > r1 || r < l1)
        return nul ;
    if(l1 <= l && r <= r1)
        return sg_b[v] ;
    int mid = (l + r) >> 1 ;
    return mrg(get_all_b(l, mid, l1, r1, v * 2), get_all_b(mid + 1, r, l1, r1, v * 2 + 1)) ;
}
signed main()
{
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    cin >> n ;
    for(int i = 1 ; i < n ; i++)
    {
        cin >> c[i] ;
        if(c[i] > 20)flag = 1 ;
    }
    for(int i = 1 ; i <= n ; i++)
    {
        int b ;
        cin >> b ;
        sm += b ;
        for(int j = 1 ; j <= b ; j++)
        {
            int a ;
            cin >> a ;
            if(a > 20)flag = 1 ;
            ks[i].push_back(a) ;
        }
    }
    cin >> q ;
    if(n <= 5000 && sm <= 5000)
    {
        for(int i = 1 ; i <= n ; i++)
            bfs(i) ;
        for(int i = 1 ; i <= q ; i++)
        {
            int x, y ;
            cin >> x >> y ;
            if(us[x][y])
                cout << "YES\n" ;
            else
                cout << "NO\n" ;
        }
        return 0 ;
    }
    if(n <= 1e5 && !flag)
    {
        build(1, NSS, 1) ;
        while(q--)
        {
            bool abu[21] = {} ;
            bool fl = 1 ;
            int x, y ;
            cin >> x >> y ;
            int lf = x, rg = x ;
            for(int j : ks[x])
                abu[j] = 1 ;
            while(fl)
            {
//                cout<<lf<< ' '<<rg<<'\n' ;
                fl ^= 1 ;
                vector<int> vl, vr ;
                int l = 0, r = lf ;
                while(l + 1 < r)
                {
                    bool check = 0 ;
                    int mid = (l + r) >> 1 ;
                    vl = get_all(1, NSS, mid, lf - 1, 1) ;
                    for(int j : vl)
                        if(!abu[j])check = 1 ;
//                    cout<<"1- "<<check<<' '<<mid << '\n';
                    if(check)
                        l = mid ;
                    else
                        r = mid ;
                }
//                cout << l << ' ' << r << '\n' ;
                if(r < lf)
                {
                    vl = get_all_b(1, NSS, r, lf - 1, 1) ;
                    for(int j : vl)
                    {
//                        cout << "1+ " << j << '\n' ;
                        abu[j] = 1 ;
                    }
                    lf = r ;
                    fl = 1 ;
                }
                l = rg - 1, r = n ;
                while(l + 1 < r)
                {
                    bool check = 0 ;
                    int mid = (l + r) >> 1 ;
//                    cout<<"2- "<<check<<' '<<mid << '\n';
                    vr = get_all(1, NSS, rg, mid, 1) ;
                    for(int j : vr)
                    {
                        if(!abu[j])check = 1 ;
                    }
                    if(check)
                        r = mid ;
                    else
                        l = mid ;
                }
//                cout << l << ' ' << r << '\n' ;
                if(l >= rg)
                {
                    vr = get_all_b(1, NSS, rg + 1, l + 1, 1) ;
                    for(int j : vr)
                        abu[j] = 1 ;
                    fl = 1 ;
                    rg = l + 1 ;
                }
//                cout<<"_____________________\n" ;
            }
            if(lf <= y && y <= rg)
                cout << "YES\n" ;
            else
                cout << "NO\n" ;
        }
        return 0 ;
    }
    return 0 ;
}

Compilation message

long_mansion.cpp: In function 'std::vector<int> mrg(std::vector<int>, std::vector<int>)':
long_mansion.cpp:49:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     while(uk1 < a.size() || uk2 < b.size())
      |           ~~~~^~~~~~~~~~
long_mansion.cpp:49:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     while(uk1 < a.size() || uk2 < b.size())
      |                             ~~~~^~~~~~~~~~
long_mansion.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         if(uk1 < a.size())
      |            ~~~~^~~~~~~~~~
long_mansion.cpp:54:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         if(uk2 < b.size())
      |            ~~~~^~~~~~~~~~
long_mansion.cpp:58:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         if(uk1 < a.size() && a[uk1] == mn)
      |            ~~~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 33108 KB Output is correct
2 Correct 108 ms 38224 KB Output is correct
3 Correct 223 ms 48368 KB Output is correct
4 Correct 37 ms 33224 KB Output is correct
5 Correct 367 ms 34740 KB Output is correct
6 Correct 142 ms 33744 KB Output is correct
7 Correct 90 ms 33448 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 33108 KB Output is correct
2 Correct 108 ms 38224 KB Output is correct
3 Correct 223 ms 48368 KB Output is correct
4 Correct 37 ms 33224 KB Output is correct
5 Correct 367 ms 34740 KB Output is correct
6 Correct 142 ms 33744 KB Output is correct
7 Correct 90 ms 33448 KB Output is correct
8 Correct 135 ms 34956 KB Output is correct
9 Correct 94 ms 34788 KB Output is correct
10 Correct 215 ms 40228 KB Output is correct
11 Correct 388 ms 50480 KB Output is correct
12 Correct 129 ms 31388 KB Output is correct
13 Correct 97 ms 35104 KB Output is correct
14 Correct 112 ms 35020 KB Output is correct
15 Correct 284 ms 35860 KB Output is correct
16 Correct 437 ms 36944 KB Output is correct
17 Correct 95 ms 34988 KB Output is correct
18 Correct 110 ms 35180 KB Output is correct
19 Correct 147 ms 35380 KB Output is correct
20 Correct 432 ms 36628 KB Output is correct
21 Correct 415 ms 36996 KB Output is correct
22 Correct 384 ms 36464 KB Output is correct
23 Correct 210 ms 35264 KB Output is correct
24 Correct 192 ms 35488 KB Output is correct
25 Correct 158 ms 35240 KB Output is correct
26 Correct 109 ms 35004 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 33108 KB Output is correct
2 Correct 108 ms 38224 KB Output is correct
3 Correct 223 ms 48368 KB Output is correct
4 Correct 37 ms 33224 KB Output is correct
5 Correct 367 ms 34740 KB Output is correct
6 Correct 142 ms 33744 KB Output is correct
7 Correct 90 ms 33448 KB Output is correct
8 Correct 135 ms 34956 KB Output is correct
9 Correct 94 ms 34788 KB Output is correct
10 Correct 215 ms 40228 KB Output is correct
11 Correct 388 ms 50480 KB Output is correct
12 Correct 129 ms 31388 KB Output is correct
13 Correct 97 ms 35104 KB Output is correct
14 Correct 112 ms 35020 KB Output is correct
15 Correct 284 ms 35860 KB Output is correct
16 Correct 437 ms 36944 KB Output is correct
17 Correct 95 ms 34988 KB Output is correct
18 Correct 110 ms 35180 KB Output is correct
19 Correct 147 ms 35380 KB Output is correct
20 Correct 432 ms 36628 KB Output is correct
21 Correct 415 ms 36996 KB Output is correct
22 Correct 384 ms 36464 KB Output is correct
23 Correct 210 ms 35264 KB Output is correct
24 Correct 192 ms 35488 KB Output is correct
25 Correct 158 ms 35240 KB Output is correct
26 Correct 109 ms 35004 KB Output is correct
27 Execution timed out 3072 ms 79544 KB Time limit exceeded
28 Halted 0 ms 0 KB -