oj.uz

답안 #1024216

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1024216 2024-07-15T16:32:32 Z ksu2009en 늑대인간 (IOI18_werewolf) C++17
34 / 100
 1642 ms 49356 KB 
#include "werewolf.h"
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>

using namespace std;
typedef int ll;

vector<ll> d[200007];

bool used1[200007], used2[200007];

ll lim = 0;

void dfs1(ll v){
    if(v < lim)
        return;
    
    used1[v] = true;
    for(auto i: d[v]){
        if(!used1[i] && i >= lim)
            dfs1(i);
    }
}

void dfs2(ll v){
    if(v > lim)
        return;
    
    used2[v] = true;
    for(auto i: d[v]){
        if(!used2[i] && i <= lim)
            dfs2(i);
    }
}

vector<ll> ord;

void dfs(ll v, ll par){
    ord.push_back(v);
    
    for(auto i: d[v])
        if(i != par)
            dfs(i, v);
}

ll a[200007];

pair<ll, ll> t[800007];

void build(ll v, ll l, ll r){
    if(l == r){
        t[v] = {a[l], a[l]};
        return;
    }
    
    ll mid = (l + r) >> 1;
    build(2 * v, l, mid);
    build(2 * v + 1, mid + 1, r);
    
    t[v].first = min(t[2 * v].first, t[2 * v + 1].first);
    t[v].second = max(t[2 * v].second, t[2 * v + 1].second);
}

ll get(ll v, ll l, ll r, ll ql, ll qr, bool mn){
    if(r < ql || qr < l)
        return (mn ? (ll)(1e9) : (ll)(-1e9));
    
    if(ql <= l && r <= qr)
        return (mn ? t[v].first : t[v].second);
    
    ll mid = (l + r) >> 1;
    if(mn)
        return min(get(2 * v, l, mid, ql, qr, mn), get(2 * v + 1, mid + 1, r, ql, qr, mn));
    
    return max(get(2 * v, l, mid, ql, qr, mn), get(2 * v + 1, mid + 1, r, ql, qr, mn));
}

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) {
    
    ll q = l.size();
    
    for(int i = 0; i < x.size(); i++){
        d[x[i]].push_back(y[i]);
        d[y[i]].push_back(x[i]);
    }
    
    vector<int> ans;
    
    if(x.size() == n - 1){
        for(int i = 0; i < n; i++){
            if(d[i].size() == 1){
                dfs(i, -1);
                break;
            }
        }
        
        vector<ll> pos(n + 1);
        for(int i = 0; i < n; i++){
            a[i + 1] = ord[i] + 1;
            
            pos[a[i + 1]] = i + 1;
        }
        
        for(int i = 0; i < q; i++)
            s[i]++, e[i]++, l[i]++, r[i]++;
        
        build(1, 1, n);
        
        for(int i = 0; i < q; i++){
            ll a = pos[s[i]], b = pos[e[i]];
            
            ll p1 = 0, p2 = 0;
            
            ll l0 = 1, r0 = n;
            while(l0 < r0){
                ll mid = (l0 + r0 + 1) >> 1;
                
                ll pos = 0;
                if(a < b)
                    pos = a + mid - 1;
                else
                    pos = a - mid + 1;
                
                if(get(1, 1, n, min(a, pos), max(a, pos), true) < l[i]){
                    r0 = mid - 1;
                }
                else
                    l0 = mid;
            }
            
            if(a < b)
                p1 = a + l0 - 1;
            else
                p1 = a - l0 + 1;
            
            l0 = 1, r0 = n;
            while(l0 < r0){
                ll mid = (l0 + r0 + 1) >> 1;
                
                ll pos = 0;
                if(a < b)
                    pos = b - mid + 1;
                else
                    pos = b + mid - 1;
                
                if(get(1, 1, n, min(b, pos), max(b, pos), false) > r[i]){
                    r0 = mid - 1;
                }
                else
                    l0 = mid;
            }
            
            if(a < b)
                p2 = b - l0 + 1;
            else
                p2 = b + l0 - 1;
            
//            cout << l0 << endl;
//            cout << p1 << ' ' << p2 << endl;
//            cout << get(1, 1, n, 1, n, true) << endl;
            
            if(a < b){
                if(p1 >= p2)
                    ans.push_back(1);
                else
                    ans.push_back(0);
            }
            else{
                if(p1 <= p2)
                    ans.push_back(1);
                else
                    ans.push_back(0);
            }
        }
        
        return ans;
    }
    
    for(int i = 0; i < q; i++){
        lim = l[i];
        
        dfs1(s[i]);
        lim = r[i];
        dfs2(e[i]);
        
        int res = 0;
        for(int j = 0; j < n; j++){
            if(used1[j] && used2[j]){
                res = 1;
            }
            
            used1[j] = used2[j] = 0;
        }
        
        ans.push_back(res);
    }
    
    return ans;
}
/*
 6 6 3
 0 3
 3 1
 3 4
 1 2
 2 5
 1 5
 4 2 1 2
 4 2 2 2
 5 4 3 4
 
 */

/*
 6 6 1
 0 3
 3 1
 3 4
 1 2
 2 5
 1 5
 4 2 1 2
 
 4 2 2 2
 5 4 3 4
 */

/*
 4 3 1
 3 0
 0 1
 1 2
 3 2 2 2
 
 */
/*
 4 3 1
 3 1
 1 0
 2 0
 3 2 1 2
 
 */

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:99:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for(int i = 0; i < x.size(); i++){
      |                    ~~^~~~~~~~~~
werewolf.cpp:106:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  106 |     if(x.size() == n - 1){
      |        ~~~~~~~~~^~~~~~~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6232 KB Output is correct
2 Incorrect 2 ms 8284 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6232 KB Output is correct
2 Incorrect 2 ms 8284 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1506 ms 40756 KB Output is correct
2 Correct 1329 ms 49348 KB Output is correct
3 Correct 1381 ms 49092 KB Output is correct
4 Correct 1430 ms 49356 KB Output is correct
5 Correct 1450 ms 49096 KB Output is correct
6 Correct 1475 ms 49160 KB Output is correct
7 Correct 1635 ms 48940 KB Output is correct
8 Correct 1349 ms 49052 KB Output is correct
9 Correct 1172 ms 49080 KB Output is correct
10 Correct 1315 ms 49128 KB Output is correct
11 Correct 1368 ms 49020 KB Output is correct
12 Correct 1291 ms 48948 KB Output is correct
13 Correct 1609 ms 49096 KB Output is correct
14 Correct 1614 ms 49072 KB Output is correct
15 Correct 1642 ms 49044 KB Output is correct
16 Correct 1625 ms 49144 KB Output is correct
17 Correct 1495 ms 49108 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6232 KB Output is correct
2 Incorrect 2 ms 8284 KB Output isn't correct
3 Halted 0 ms 0 KB -