oj.uz

Submission #891244

# Submission time Handle Problem Language Result Execution time Memory
891244 2023-12-22T14:54:01 Z vjudge1 Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 60664 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(pdr < dr.size() && 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;
      |                           ~~~~^~~~~~~~~~~
werewolf.cpp:81:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |                     if(pdr < dr.size() && dr[pdr] == st[i]) ok = 1;
      |                        ~~~~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 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 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 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 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 672 ms 1620 KB Output is correct
11 Correct 531 ms 1424 KB Output is correct
12 Correct 268 ms 1488 KB Output is correct
13 Correct 312 ms 1372 KB Output is correct
14 Correct 219 ms 1348 KB Output is correct
15 Correct 610 ms 1700 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4016 ms 60664 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 344 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 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 672 ms 1620 KB Output is correct
11 Correct 531 ms 1424 KB Output is correct
12 Correct 268 ms 1488 KB Output is correct
13 Correct 312 ms 1372 KB Output is correct
14 Correct 219 ms 1348 KB Output is correct
15 Correct 610 ms 1700 KB Output is correct
16 Execution timed out 4016 ms 60664 KB Time limit exceeded
17 Halted 0 ms 0 KB -