oj.uz

Submission #801609

# Submission time Handle Problem Language Result Execution time Memory
801609 2023-08-02T06:54:00 Z vjudge1 Long Mansion (JOI17_long_mansion) C++14
10 / 100
 3000 ms 51376 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(c.size() < 20 && (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()
{
	for(int i = 0 ; i < NSS ; i++)
    {
        sg[i + NSS].push_back(c[i]) ;
        sg_b[i + NSS] = ks[i] ;
    }
	for(int i = NSS - 1 ; i > 0 ; i--)
    {
        sg[i] = mrg(sg[i * 2], sg[i * 2 + 1]) ;
        sg_b[i] = mrg(sg_b[i * 2], sg_b[i * 2 + 1]) ;
    }
}
vector<int> get_all(int l1, int r1)
{
	l1 += NSS ;
	r1 += NSS ;
	vector<int> res ;
	while(l1 <= r1)
    {
		if(l1 % 2 == 1)
            res = mrg(res, sg[l1++]) ;
		if(r1 % 2 == 0)
            res = mrg(res, sg[r1--]) ;
        l1 >>= 1 ;
        r1 >>= 1 ;
	}
	return res ;
}
vector<int> get_all_b(int l1, int r1)
{
	l1 += NSS ;
	r1 += NSS ;
	vector<int> res ;
	while(l1 <= r1)
    {
		if(l1 % 2 == 1)
            res = mrg(res, sg_b[l1++]) ;
		if(r1 % 2 == 0)
            res = mrg(res, sg_b[r1--]) ;
        l1 >>= 1 ;
        r1 >>= 1 ;
	}
	return res ;
}
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 <= 100000 && !flag)
    {
        build() ;
        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(mid, lf - 1) ;
                    for(int j : vl)
                    {
                        if(!abu[j])check = 1 ;
                    }
                    if(check)
                        l = mid ;
                    else
                        r = mid ;
                }
                if(r < lf)
                {
                    vl = get_all_b(r, lf - 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(rg, mid) ;
                    for(int j : vr)
                        if(!abu[j])check = 1 ;
                    if(check)
                        r = mid ;
                    else
                        l = mid ;
                }
                if(l >= rg)
                {
                    vr = get_all_b(rg + 1, l + 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:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     while(c.size() < 20 && (uk1 < a.size() || uk2 < b.size()))
      |                             ~~~~^~~~~~~~~~
long_mansion.cpp:53:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     while(c.size() < 20 && (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 22 ms 33008 KB Output is correct
2 Correct 116 ms 38144 KB Output is correct
3 Correct 221 ms 48348 KB Output is correct
4 Correct 30 ms 33100 KB Output is correct
5 Correct 359 ms 34728 KB Output is correct
6 Correct 134 ms 33612 KB Output is correct
7 Correct 85 ms 33444 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 33008 KB Output is correct
2 Correct 116 ms 38144 KB Output is correct
3 Correct 221 ms 48348 KB Output is correct
4 Correct 30 ms 33100 KB Output is correct
5 Correct 359 ms 34728 KB Output is correct
6 Correct 134 ms 33612 KB Output is correct
7 Correct 85 ms 33444 KB Output is correct
8 Correct 133 ms 34700 KB Output is correct
9 Correct 109 ms 34612 KB Output is correct
10 Correct 209 ms 39972 KB Output is correct
11 Correct 337 ms 50232 KB Output is correct
12 Correct 129 ms 31100 KB Output is correct
13 Correct 92 ms 34816 KB Output is correct
14 Correct 107 ms 34824 KB Output is correct
15 Correct 253 ms 35648 KB Output is correct
16 Correct 435 ms 36740 KB Output is correct
17 Correct 90 ms 34808 KB Output is correct
18 Correct 107 ms 34916 KB Output is correct
19 Correct 151 ms 35128 KB Output is correct
20 Correct 429 ms 36308 KB Output is correct
21 Correct 458 ms 36736 KB Output is correct
22 Correct 405 ms 36168 KB Output is correct
23 Correct 206 ms 35004 KB Output is correct
24 Correct 184 ms 35060 KB Output is correct
25 Correct 148 ms 35020 KB Output is correct
26 Correct 132 ms 34792 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 33008 KB Output is correct
2 Correct 116 ms 38144 KB Output is correct
3 Correct 221 ms 48348 KB Output is correct
4 Correct 30 ms 33100 KB Output is correct
5 Correct 359 ms 34728 KB Output is correct
6 Correct 134 ms 33612 KB Output is correct
7 Correct 85 ms 33444 KB Output is correct
8 Correct 133 ms 34700 KB Output is correct
9 Correct 109 ms 34612 KB Output is correct
10 Correct 209 ms 39972 KB Output is correct
11 Correct 337 ms 50232 KB Output is correct
12 Correct 129 ms 31100 KB Output is correct
13 Correct 92 ms 34816 KB Output is correct
14 Correct 107 ms 34824 KB Output is correct
15 Correct 253 ms 35648 KB Output is correct
16 Correct 435 ms 36740 KB Output is correct
17 Correct 90 ms 34808 KB Output is correct
18 Correct 107 ms 34916 KB Output is correct
19 Correct 151 ms 35128 KB Output is correct
20 Correct 429 ms 36308 KB Output is correct
21 Correct 458 ms 36736 KB Output is correct
22 Correct 405 ms 36168 KB Output is correct
23 Correct 206 ms 35004 KB Output is correct
24 Correct 184 ms 35060 KB Output is correct
25 Correct 148 ms 35020 KB Output is correct
26 Correct 132 ms 34792 KB Output is correct
27 Execution timed out 3040 ms 51376 KB Time limit exceeded
28 Halted 0 ms 0 KB -