oj.uz

Submission #891240

# Submission time Handle Problem Language Result Execution time Memory
891240 2023-12-22T14:51:20 Z vjudge1 Werewolf (IOI18_werewolf) C++17
0 / 100
 4000 ms 68720 KB 
#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

struct UF {
    int n;
    vi e;
    vector<vi> el;
    UF(int N) : n(N), e(N, -1), el(N) {
        for(int i = 0; i < n; ++i) el[i].push_back(i);
    }

    int repr(int u) {
        while(e[u] >= 0) u = e[u];
        return u;
    }

    void join(int u, int v) {
        u = repr(u);
        v = repr(v);
        if(u == v) return;
        if(e[u] > e[v]) swap(u, v);
        e[u] += e[v];
        for(auto it : el[v])
            el[u].push_back(it);
        e[v] = u;
    }

    void clear() {
        for(auto &it : e) it = -1;
        for(int i = 0; i < n; ++i) {
            el[i].clear();
            el[i].push_back(i);
        }
    }

    vi acces(int u) {
        return el[repr(u)];
    }
};

vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
    vector<vi> adj(N);
    for(int i = 0; i < (int)(X.size()); ++i) {
        adj[X[i]].push_back(Y[i]);
        adj[Y[i]].push_back(X[i]);
    }
    int q = L.size();
    vector<vi> QL(N);
    for(int i = 0; i < q; ++i) {
        QL[L[i]].push_back(i);
    }
/// n <= 3000   m <= 6000  q <= 3000
    UF S1(N), S2(N); 
    
    vector<int> Re(q, 0);
    for(int l = N - 1; l >= 0; --l) {
        for(auto it : adj[l])
            if(it > l)
                S1.join(it, l);
        sort(QL[l].begin(), QL[l].end(), [&](auto a, auto b) { return R[a] < R[b]; });
        int p = 0;
        S2.clear();
        for(int r = 0; r < N; ++r) {
            for(auto it : adj[r])  {
                if(it < r)
                    S2.join(it, r);
            }
            while(p < QL[l].size() && R[QL[l][p]] == r) {
                int id = QL[l][p];
                vi st = S1.acces(S[id]);
                vi dr = S2.acces(E[id]);
                sort(st.begin(), st.end());
                sort(dr.begin(), dr.end());
                int pdr = 0, ok = 0;
                for(int i = 0; i < st.size(); ++i) {
                    while(pdr < dr.size() && dr[pdr] < st[i]) ++pdr;
                    if(dr[pdr] == st[i]) ok = 1;
                }
                Re[id] = ok;
                ++p;
            }
        }
    }
    return Re;
}

Compilation message

werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:72:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             while(p < QL[l].size() && R[QL[l][p]] == r) {
      |                   ~~^~~~~~~~~~~~~~
werewolf.cpp:79:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |                 for(int i = 0; i < st.size(); ++i) {
      |                                ~~^~~~~~~~~~~
werewolf.cpp:80:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |                     while(pdr < dr.size() && dr[pdr] < st[i]) ++pdr;
      |                           ~~~~^~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Incorrect 1 ms 440 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Incorrect 1 ms 440 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4043 ms 68720 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Incorrect 1 ms 440 KB Output isn't correct
9 Halted 0 ms 0 KB -