oj.uz

답안 #801602

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
801602 2023-08-02T06:51:00 Z vjudge1 Long Mansion (JOI17_long_mansion) C++14
10 / 100
 3000 ms 113036 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 ;
bool flag, us[NS + 1][NS + 1] ;
int n, q, sm, c[N + 1] ;
vector<int> sg[2 * N + 1], sg_b[2 * N + 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 < N ; i++)
    {
        sg[i + N].push_back(c[i]) ;
        sg_b[i + N] = ks[i] ;
    }
	for(int i = N - 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 += N ;
	r1 += N ;
	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 += N ;
	r1 += N ;
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 69972 KB Output is correct
2 Correct 125 ms 75188 KB Output is correct
3 Correct 229 ms 85300 KB Output is correct
4 Correct 47 ms 70100 KB Output is correct
5 Correct 358 ms 71632 KB Output is correct
6 Correct 150 ms 70592 KB Output is correct
7 Correct 105 ms 70376 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 69972 KB Output is correct
2 Correct 125 ms 75188 KB Output is correct
3 Correct 229 ms 85300 KB Output is correct
4 Correct 47 ms 70100 KB Output is correct
5 Correct 358 ms 71632 KB Output is correct
6 Correct 150 ms 70592 KB Output is correct
7 Correct 105 ms 70376 KB Output is correct
8 Correct 139 ms 71696 KB Output is correct
9 Correct 106 ms 71528 KB Output is correct
10 Correct 229 ms 76884 KB Output is correct
11 Correct 350 ms 87200 KB Output is correct
12 Correct 138 ms 68044 KB Output is correct
13 Correct 103 ms 71756 KB Output is correct
14 Correct 112 ms 71800 KB Output is correct
15 Correct 267 ms 72516 KB Output is correct
16 Correct 433 ms 73692 KB Output is correct
17 Correct 105 ms 71744 KB Output is correct
18 Correct 125 ms 71832 KB Output is correct
19 Correct 156 ms 72008 KB Output is correct
20 Correct 442 ms 73256 KB Output is correct
21 Correct 421 ms 73744 KB Output is correct
22 Correct 381 ms 73088 KB Output is correct
23 Correct 234 ms 71944 KB Output is correct
24 Correct 196 ms 71980 KB Output is correct
25 Correct 176 ms 72036 KB Output is correct
26 Correct 122 ms 71748 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3063 ms 113036 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 69972 KB Output is correct
2 Correct 125 ms 75188 KB Output is correct
3 Correct 229 ms 85300 KB Output is correct
4 Correct 47 ms 70100 KB Output is correct
5 Correct 358 ms 71632 KB Output is correct
6 Correct 150 ms 70592 KB Output is correct
7 Correct 105 ms 70376 KB Output is correct
8 Correct 139 ms 71696 KB Output is correct
9 Correct 106 ms 71528 KB Output is correct
10 Correct 229 ms 76884 KB Output is correct
11 Correct 350 ms 87200 KB Output is correct
12 Correct 138 ms 68044 KB Output is correct
13 Correct 103 ms 71756 KB Output is correct
14 Correct 112 ms 71800 KB Output is correct
15 Correct 267 ms 72516 KB Output is correct
16 Correct 433 ms 73692 KB Output is correct
17 Correct 105 ms 71744 KB Output is correct
18 Correct 125 ms 71832 KB Output is correct
19 Correct 156 ms 72008 KB Output is correct
20 Correct 442 ms 73256 KB Output is correct
21 Correct 421 ms 73744 KB Output is correct
22 Correct 381 ms 73088 KB Output is correct
23 Correct 234 ms 71944 KB Output is correct
24 Correct 196 ms 71980 KB Output is correct
25 Correct 176 ms 72036 KB Output is correct
26 Correct 122 ms 71748 KB Output is correct
27 Execution timed out 3063 ms 113036 KB Time limit exceeded
28 Halted 0 ms 0 KB -