oj.uz

답안 #580810

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
580810 2022-06-21T21:17:40 Z definitelynotmee 늑대인간 (IOI18_werewolf) C++17
49 / 100
 518 ms 64828 KB 
#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;

std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    
    matrix<int> g(N);
    for(int i = 0; i < X.size(); i++){
        g[X[i]].push_back(Y[i]);
        g[Y[i]].push_back(X[i]);
    }
    int Q = S.size();
    std::vector<int> ans(Q);
    
    if(N <= 3000){
        
        vector<int> c1(N), c2(N);
        auto dfs =[&](int id, int l, int r,vector<int>&check, auto dfs)->void{
            check[id] = 1;
            for(int i : g[id]){
                if(check[i] || i > r || i < l)
                    continue;
                dfs(i,l,r,check,dfs);
            }
        };

        for(int i = 0; i < Q; i++){
            fill(all(c1),0);
            fill(all(c2),0);
            dfs(S[i],L[i],N,c1,dfs);
            dfs(E[i],0,R[i],c2,dfs);
            for(int j = 0; j < N; j++){
                ans[i]|=c1[j]&&c2[j];
            }
        }
    } else {
        vector<int> v;
        v.reserve(N);
        auto dfs =[&](int id, int last, auto dfs)->void{
            for(int i : g[id])
                if(i != last) dfs(i,id,dfs);
            v.push_back(id);
        };

        for(int i = 0; i < N; i++){
            if(g[i].size() == 1){
                dfs(i,-1,dfs);
                break;
            }
        }

        assert(v.size() == N);

        vector<int> inv(N);
        for(int i = 0; i < N; i++)
            inv[v[i]] = i;
        
        matrix<int> smin(20,vector<int>(N)), smax(20,vector<int>(N));
        for(int i = 0; i < N; i++)
            smin[0][i] = v[i], smax[0][i] = v[i];
        
        for(int i = 1; i < 20; i++){
            for(int j = 0; j+(1<<i) <= N; j++){
                smin[i][j] = min(smin[i-1][j],smin[i-1][j+(1<<i-1)]);
                smax[i][j] = max(smax[i-1][j],smax[i-1][j+(1<<i-1)]);
            }
        }

        auto qmin =[&](int l, int r){
            int logg = log2(r-l+1);
            return min(smin[logg][l],smin[logg][r-(1<<logg)+1]);
        };
        auto qmax =[&](int l, int r){
            int logg = log2(r-l+1);
            return max(smax[logg][l],smax[logg][r-(1<<logg)+1]);
        };

        for(int i = 0; i < Q; i++){
            int a = inv[S[i]], b = inv[E[i]];
            if(a < b){
                int ini = a, fim = b;
                while(ini!=fim){
                    //cout << 'a'<< ini << ' ' << fim << endl;
                    int m = (ini+fim+1)>>1;
                    if(qmin(a,m) >= L[i])
                        ini = m;
                    else fim = m-1;
                }
                //cout << "a->" << ini << '\n';
                ans[i] = qmax(ini,b) <= R[i];
            } else {
                int ini = b, fim = a;
                while(ini!=fim){
                    //cout <<'b'<< ini << ' ' << fim << endl;
                    int m = (ini+fim)>>1;
                    if(qmin(m,a) >= L[i])
                        fim = m;
                    else ini = m+1;
                }
                //cout << "b->" << ini << '\n';
                ans[i] = qmax(b,ini) <= R[i];
            }
        }
    }
    
    return ans;
}

Compilation message

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:18:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(int i = 0; i < X.size(); i++){
      |                    ~~^~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from werewolf.cpp:2:
werewolf.cpp:62:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |         assert(v.size() == N);
      |                ~~~~~~~~~^~~~
werewolf.cpp:74:64: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   74 |                 smin[i][j] = min(smin[i-1][j],smin[i-1][j+(1<<i-1)]);
      |                                                               ~^~
werewolf.cpp:75:64: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   75 |                 smax[i][j] = max(smax[i-1][j],smax[i-1][j+(1<<i-1)]);
      |                                                               ~^~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 280 ms 628 KB Output is correct
11 Correct 185 ms 616 KB Output is correct
12 Correct 22 ms 672 KB Output is correct
13 Correct 301 ms 640 KB Output is correct
14 Correct 236 ms 620 KB Output is correct
15 Correct 247 ms 728 KB Output is correct

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 518 ms 62136 KB Output is correct
2 Correct 348 ms 62292 KB Output is correct
3 Correct 343 ms 62360 KB Output is correct
4 Correct 423 ms 64756 KB Output is correct
5 Correct 448 ms 64652 KB Output is correct
6 Correct 449 ms 64784 KB Output is correct
7 Correct 444 ms 64828 KB Output is correct
8 Correct 381 ms 64700 KB Output is correct
9 Correct 290 ms 64648 KB Output is correct
10 Correct 312 ms 64648 KB Output is correct
11 Correct 337 ms 64588 KB Output is correct
12 Correct 330 ms 64712 KB Output is correct
13 Correct 409 ms 64712 KB Output is correct
14 Correct 417 ms 64648 KB Output is correct
15 Correct 445 ms 64712 KB Output is correct
16 Correct 357 ms 64712 KB Output is correct
17 Correct 486 ms 64780 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 280 ms 628 KB Output is correct
11 Correct 185 ms 616 KB Output is correct
12 Correct 22 ms 672 KB Output is correct
13 Correct 301 ms 640 KB Output is correct
14 Correct 236 ms 620 KB Output is correct
15 Correct 247 ms 728 KB Output is correct
16 Correct 518 ms 62136 KB Output is correct
17 Correct 348 ms 62292 KB Output is correct
18 Correct 343 ms 62360 KB Output is correct
19 Correct 423 ms 64756 KB Output is correct
20 Correct 448 ms 64652 KB Output is correct
21 Correct 449 ms 64784 KB Output is correct
22 Correct 444 ms 64828 KB Output is correct
23 Correct 381 ms 64700 KB Output is correct
24 Correct 290 ms 64648 KB Output is correct
25 Correct 312 ms 64648 KB Output is correct
26 Correct 337 ms 64588 KB Output is correct
27 Correct 330 ms 64712 KB Output is correct
28 Correct 409 ms 64712 KB Output is correct
29 Correct 417 ms 64648 KB Output is correct
30 Correct 445 ms 64712 KB Output is correct
31 Correct 357 ms 64712 KB Output is correct
32 Correct 486 ms 64780 KB Output is correct
33 Incorrect 432 ms 57980 KB Output isn't correct
34 Halted 0 ms 0 KB -