oj.uz

Submission #1024222

# Submission time Handle Problem Language Result Execution time Memory
1024222 2024-07-15T17:02:20 Z ksu2009en Werewolf (IOI18_werewolf) C++14
0 / 100
 178 ms 33872 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;

pair<int, int> t[200007];
ll lead[200007];

ll findlead(ll v){
    if(lead[v] == v)
        return v;
    
    return lead[v] = findlead(lead[v]);
}

void unite(ll a, ll b){
    a = findlead(a), b = findlead(b);
    
    if(a == b)
        return;
    
    t[b].first = min(t[b].first, t[a].first);
    t[b].second = max(t[b].second, t[a].second);
    
    lead[a] = b;
}

vector<ll> d[200007];

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 < q; i++)
        s[i]++, e[i]++, l[i]++, r[i]++;
    
    for(int i = 0; i < x.size(); i++){
        x[i]++, y[i]++;
        
        d[min(x[i], y[i])].push_back(max(x[i], y[i]));
    }
    
    vector<int> ans(q);
    
    vector<vector<int>> g(n + 1);
    for(int i = 0; i < q; i++)
        g[l[i]].push_back(i);
    
    for(int i = 1; i <= n; i++){
        lead[i] = i;
        t[i].first = t[i].second = i;
    }
    
    for(int i = n; i >= 1; i--){
        for(auto j: d[i])
            unite(i, j);
        
        for(auto j: g[i]){
            if(t[findlead(x[j])].first <= r[j])
                ans[j]++;
        }
    }
    
    for(int i = 1; i <= n; i++){
        lead[i] = i;
        t[i].first = t[i].second = i;
    }
    
    for(int i = 1; i <= n; i++)
        g[i].clear();
    
    for(int i = 0; i < q; i++){
        g[r[i]].push_back(i);
    }
    
    for(int i = 1; i <= n; i++)
        d[i].clear();
    
    for(int i = 0; i < x.size(); i++){
        d[max(x[i], y[i])].push_back(min(x[i], y[i]));
    }
    
    for(int i = 1; i <= n; i++){
        for(auto j: d[i])
            unite(i, j);
        
        for(auto j: g[i]){
            if(t[findlead(y[j])].first >= l[j])
                ans[j]++;
        }
    }
    
    for(int i = 0; i < q; i++)
        ans[i] = (ans[i] == 2 ? 1 : 0);
    
    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:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int i = 0; i < x.size(); i++){
      |                    ~~^~~~~~~~~~
werewolf.cpp:97:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for(int i = 0; i < x.size(); i++){
      |                    ~~^~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 178 ms 33872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6748 KB Output isn't correct
2 Halted 0 ms 0 KB -