oj.uz

Submission #801487

# Submission time Handle Problem Language Result Execution time Memory
801487 2023-08-02T06:19:32 Z vjudge1 Long Mansion (JOI17_long_mansion) C++
10 / 100
 3000 ms 77792 KB 
#include<iostream>
#include<map>
#include<vector>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
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)
            {
                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 ;
                    if(check)
                        l = mid ;
                    else
                        r = mid ;
                }
                if(r < lf)
                {
                    vl = get_all_b(1, NSS, r, lf - 1, 1) ;
                    for(int j : vl)
                        abu[j] = 1 ;
                    lf = r ;
                    fl = 1 ;
                }
                l = rg - 1, r = n ;
                while(l + 1 < r)
                {
                    bool check = 0 ;
                    int mid = (l + r) >> 1 ;
                    vr = get_all(1, NSS, rg, mid, 1) ;
                    for(int j : vr)
                        if(!abu[j])check = 1 ;
                    if(check)
                        r = mid ;
                    else
                        l = mid ;
                }
                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 ;
                }
            }
            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:53:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     while(uk1 < a.size() || uk2 < b.size())
      |           ~~~~^~~~~~~~~~
long_mansion.cpp:53:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     while(uk1 < a.size() || uk2 < b.size())
      |                             ~~~~^~~~~~~~~~
long_mansion.cpp:56:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         if(uk1 < a.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(uk2 < b.size())
      |            ~~~~^~~~~~~~~~
long_mansion.cpp:62:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         if(uk1 < a.size() && a[uk1] == mn)
      |            ~~~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 32996 KB Output is correct
2 Correct 111 ms 38136 KB Output is correct
3 Correct 230 ms 48332 KB Output is correct
4 Correct 30 ms 33176 KB Output is correct
5 Correct 352 ms 34656 KB Output is correct
6 Correct 138 ms 33684 KB Output is correct
7 Correct 88 ms 33400 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 32996 KB Output is correct
2 Correct 111 ms 38136 KB Output is correct
3 Correct 230 ms 48332 KB Output is correct
4 Correct 30 ms 33176 KB Output is correct
5 Correct 352 ms 34656 KB Output is correct
6 Correct 138 ms 33684 KB Output is correct
7 Correct 88 ms 33400 KB Output is correct
8 Correct 115 ms 34804 KB Output is correct
9 Correct 94 ms 34596 KB Output is correct
10 Correct 194 ms 39856 KB Output is correct
11 Correct 382 ms 50128 KB Output is correct
12 Correct 123 ms 31140 KB Output is correct
13 Correct 103 ms 34784 KB Output is correct
14 Correct 96 ms 34764 KB Output is correct
15 Correct 266 ms 35660 KB Output is correct
16 Correct 431 ms 36772 KB Output is correct
17 Correct 89 ms 34804 KB Output is correct
18 Correct 112 ms 34912 KB Output is correct
19 Correct 140 ms 35160 KB Output is correct
20 Correct 420 ms 36332 KB Output is correct
21 Correct 417 ms 36812 KB Output is correct
22 Correct 375 ms 36268 KB Output is correct
23 Correct 204 ms 35072 KB Output is correct
24 Correct 184 ms 35040 KB Output is correct
25 Correct 153 ms 34972 KB Output is correct
26 Correct 109 ms 34772 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 32996 KB Output is correct
2 Correct 111 ms 38136 KB Output is correct
3 Correct 230 ms 48332 KB Output is correct
4 Correct 30 ms 33176 KB Output is correct
5 Correct 352 ms 34656 KB Output is correct
6 Correct 138 ms 33684 KB Output is correct
7 Correct 88 ms 33400 KB Output is correct
8 Correct 115 ms 34804 KB Output is correct
9 Correct 94 ms 34596 KB Output is correct
10 Correct 194 ms 39856 KB Output is correct
11 Correct 382 ms 50128 KB Output is correct
12 Correct 123 ms 31140 KB Output is correct
13 Correct 103 ms 34784 KB Output is correct
14 Correct 96 ms 34764 KB Output is correct
15 Correct 266 ms 35660 KB Output is correct
16 Correct 431 ms 36772 KB Output is correct
17 Correct 89 ms 34804 KB Output is correct
18 Correct 112 ms 34912 KB Output is correct
19 Correct 140 ms 35160 KB Output is correct
20 Correct 420 ms 36332 KB Output is correct
21 Correct 417 ms 36812 KB Output is correct
22 Correct 375 ms 36268 KB Output is correct
23 Correct 204 ms 35072 KB Output is correct
24 Correct 184 ms 35040 KB Output is correct
25 Correct 153 ms 34972 KB Output is correct
26 Correct 109 ms 34772 KB Output is correct
27 Execution timed out 3068 ms 77792 KB Time limit exceeded
28 Halted 0 ms 0 KB -