oj.uz

Submission #1024218

# Submission time Handle Problem Language Result Execution time Memory
1024218 2024-07-15T16:34:12 Z ksu2009en Werewolf (IOI18_werewolf) C++17
49 / 100
 4000 ms 40752 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;
    
    ll one = 0, two = 0;
    for(int i = 0; i < n; i++){
        if(d[i].size() == 1)
            one++;
        if(d[i].size() == 2)
            two++;
    }
    if(one + two == n){
        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++){
      |                    ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6236 KB Output is correct
2 Correct 1 ms 6236 KB Output is correct
3 Correct 2 ms 6236 KB Output is correct
4 Correct 1 ms 6236 KB Output is correct
5 Correct 2 ms 6236 KB Output is correct
6 Correct 1 ms 6236 KB Output is correct
7 Correct 2 ms 6244 KB Output is correct
8 Correct 2 ms 8284 KB Output is correct
9 Correct 2 ms 6236 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6236 KB Output is correct
2 Correct 1 ms 6236 KB Output is correct
3 Correct 2 ms 6236 KB Output is correct
4 Correct 1 ms 6236 KB Output is correct
5 Correct 2 ms 6236 KB Output is correct
6 Correct 1 ms 6236 KB Output is correct
7 Correct 2 ms 6244 KB Output is correct
8 Correct 2 ms 8284 KB Output is correct
9 Correct 2 ms 6236 KB Output is correct
10 Correct 157 ms 6496 KB Output is correct
11 Correct 68 ms 6500 KB Output is correct
12 Correct 13 ms 8784 KB Output is correct
13 Correct 189 ms 6492 KB Output is correct
14 Correct 78 ms 6484 KB Output is correct
15 Correct 167 ms 6584 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1615 ms 40636 KB Output is correct
2 Correct 1412 ms 40604 KB Output is correct
3 Correct 1536 ms 40520 KB Output is correct
4 Correct 1511 ms 40644 KB Output is correct
5 Correct 1502 ms 40508 KB Output is correct
6 Correct 1522 ms 40644 KB Output is correct
7 Correct 1688 ms 40616 KB Output is correct
8 Correct 1301 ms 40512 KB Output is correct
9 Correct 1218 ms 40648 KB Output is correct
10 Correct 1272 ms 40644 KB Output is correct
11 Correct 1365 ms 40652 KB Output is correct
12 Correct 1245 ms 40508 KB Output is correct
13 Correct 1588 ms 40500 KB Output is correct
14 Correct 1476 ms 40692 KB Output is correct
15 Correct 1478 ms 40648 KB Output is correct
16 Correct 1590 ms 40752 KB Output is correct
17 Correct 1713 ms 40652 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6236 KB Output is correct
2 Correct 1 ms 6236 KB Output is correct
3 Correct 2 ms 6236 KB Output is correct
4 Correct 1 ms 6236 KB Output is correct
5 Correct 2 ms 6236 KB Output is correct
6 Correct 1 ms 6236 KB Output is correct
7 Correct 2 ms 6244 KB Output is correct
8 Correct 2 ms 8284 KB Output is correct
9 Correct 2 ms 6236 KB Output is correct
10 Correct 157 ms 6496 KB Output is correct
11 Correct 68 ms 6500 KB Output is correct
12 Correct 13 ms 8784 KB Output is correct
13 Correct 189 ms 6492 KB Output is correct
14 Correct 78 ms 6484 KB Output is correct
15 Correct 167 ms 6584 KB Output is correct
16 Correct 1615 ms 40636 KB Output is correct
17 Correct 1412 ms 40604 KB Output is correct
18 Correct 1536 ms 40520 KB Output is correct
19 Correct 1511 ms 40644 KB Output is correct
20 Correct 1502 ms 40508 KB Output is correct
21 Correct 1522 ms 40644 KB Output is correct
22 Correct 1688 ms 40616 KB Output is correct
23 Correct 1301 ms 40512 KB Output is correct
24 Correct 1218 ms 40648 KB Output is correct
25 Correct 1272 ms 40644 KB Output is correct
26 Correct 1365 ms 40652 KB Output is correct
27 Correct 1245 ms 40508 KB Output is correct
28 Correct 1588 ms 40500 KB Output is correct
29 Correct 1476 ms 40692 KB Output is correct
30 Correct 1478 ms 40648 KB Output is correct
31 Correct 1590 ms 40752 KB Output is correct
32 Correct 1713 ms 40652 KB Output is correct
33 Execution timed out 4035 ms 30544 KB Time limit exceeded
34 Halted 0 ms 0 KB -