제출 #891249

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
891249		vjudge1	늑대인간 (IOI18_werewolf)	C++17	15 / 100	666 ms	101492 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;

struct UF {
    int n;
    vi e, mi, ma;
    vector<vi> el;
    UF(int N) : n(N), e(N, -1), el(N), mi(N), ma(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];
        mi[u] = min(mi[u], mi[v]);
        ma[u] = max(ma[v], ma[u]);
        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);
        }
    }

    ii get_seg(int u) {
        u = repr(u);
        return make_pair(mi[u], ma[u]);
    }

    void setval(vi &V) {
        for(int i = 0; i < n; ++i)
            mi[i] = ma[i] = V[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(), m = X.size();
    vector<vi> QL(N);
    for(int i = 0; i < q; ++i) {
        QL[L[i]].push_back(i);
    }
/// n <= 3000   m <= 6000  q <= 3000
    if(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;
    } else {
        ///presupunem ca e o dreapta
        int capat = 0;
        for(int i = 0; i < N; ++i) {
            if(adj[i].size() == 1) capat = i;
        }
        vi valori(N, 0);
        function<void(int, int, int)> dfs0 = [&](int u, int p, int v) {
            valori[u] = v;
            for(auto it : adj[u]) {
                if(it != p) {
                    dfs0(it, u, v + 1);
                }
            }
        };
        dfs0(capat, -1, 0);
        vector<vi> QL(N), QR(N);
        for(int i = 0; i < q; ++i) {
            QL[L[i]].push_back(i);
            QR[R[i]].push_back(i);
        }
        
        vector<ii> SegL(q), SegR(q);

        UF Sol(N);
        Sol.setval(valori);
        for(int i = N - 1; i >= 0; --i) {
            for(auto it : adj[i])
                if(it > i) Sol.join(i, it);
            for(auto id : QL[i]) {
                SegL[id] = Sol.get_seg(S[id]);
            }
        }

        Sol.clear();
        Sol.setval(valori);

        for(int i = 0; i < N; ++i) {
            for(auto it : adj[i])
                if(it < i) Sol.join(i, it);
            for(auto id : QR[i]) {
                SegR[id] = Sol.get_seg(R[id]);
            }
        }

        vector<int> Re(q, 0);

        for(int i = 0; i < q; ++i) {
            if(SegL[i].second < SegR[i].first || SegR[i].second < SegL[i].first) Re[i] = 0;
            else Re[i] = 1;
        }

        return Re;
    }
}

컴파일 시 표준 에러 (stderr) 메시지

werewolf.cpp: In constructor 'UF::UF(int)':
werewolf.cpp:12:16: warning: 'UF::el' will be initialized after [-Wreorder]
   12 |     vector<vi> el;
      |                ^~
werewolf.cpp:11:11: warning:   'vi UF::mi' [-Wreorder]
   11 |     vi e, mi, ma;
      |           ^~
werewolf.cpp:13:5: warning:   when initialized here [-Wreorder]
   13 |     UF(int N) : n(N), e(N, -1), el(N), mi(N), ma(N) {
      |     ^~
werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:85:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |                 while(p < QL[l].size() && R[QL[l][p]] == r) {
      |                       ~~^~~~~~~~~~~~~~
werewolf.cpp:92:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |                     for(int i = 0; i < st.size(); ++i) {
      |                                    ~~^~~~~~~~~~~
werewolf.cpp:93:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |                         while(pdr < dr.size() && dr[pdr] < st[i]) ++pdr;
      |                               ~~~~^~~~~~~~~~~
werewolf.cpp:94:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |                         if(pdr < dr.size() && dr[pdr] == st[i]) ok = 1;
      |                            ~~~~^~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51