답안 #96094 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96094	2019-02-05T19:42:55 Z	bogdan10bos	늑대인간 (IOI18_werewolf)	C++14	100 / 100	1134 ms	104188 KB

werewolf

#include "werewolf.h"

using namespace std;

typedef pair<int, int> pii;

const int NMAX = 2e5;

int N;
vector< vector<int> > edg;

class Tree
{
public:
    int N, I;
    vector<int> f, fth[20];
    vector<int> lft, rgt, ord;
    vector< vector<int> > edg;

    int F(int x)
    {
        if(f[x] == x)   return x;
        return f[x] = F(f[x]);
    }

    void init(int _N)
    {
        N = _N;
        f.resize(N + 2);
        edg.resize(N + 2);
        for(int i = 0; i < N; i++)  f[i] = i;
        lft.resize(N + 2);
        rgt.resize(N + 2);
        for(int i = 0; i < 19; i++) fth[i].resize(N + 2);
        ord.resize(N + 2);
    }

    void add(int x, int y)
    {
        int fx = F(x);
        int fy = F(y);
        if(fx == fy)    return;

        edg[fx].push_back(fy);
        f[fy] = fx;
    }

    void DFS(int nod, int f = -1)
    {
        fth[0][nod] = f;
        for(int i = 1; i < 19; i++)
        {
            if(fth[i - 1][nod] == -1)   fth[i][nod] = -1;
            else    fth[i][nod] = fth[i - 1][ fth[i - 1][nod] ];
        }

        lft[nod] = ++I;
        ord[I] = nod;
        for(auto nxt: edg[nod])
            DFS(nxt, nod);
        rgt[nod] = I;
    }
};

Tree pfx, sfx;

class BinaryIndexedTree
{
public:
    int N;
    vector<int> aib;

    void init(int _N)
    {
        N = _N;
        aib.resize(N + 2);
    }

    void U(int pos, int val)
    {
        for(; pos <= N; pos += (pos & (-pos)))
            aib[pos] += val;
    }

    int Q(int pos)
    {
        int ans = 0;
        for(; pos > 0; pos -= (pos & (-pos)))
            ans += aib[pos];
        return ans;
    }
}aib;

vector<int> check_validity(int _N, vector<int> e1, vector<int> e2,
                           vector<int> S, vector<int> T,
                           vector<int> L, vector<int> R)
{
    N = _N;
    edg.resize(N + 2);
    for(int i = 0; i < e1.size(); i++)
    {
        int x = e1[i], y = e2[i];
        edg[x].push_back(y);
        edg[y].push_back(x);
    }

    pfx.init(N);
    for(int i = 0; i < N; i++)
        for(auto nod: edg[i])
            if(nod < i)
                pfx.add(i, nod);
    pfx.DFS(N - 1);

    sfx.init(N);
    for(int i = N - 1; i >= 0; i--)
        for(auto nod: edg[i])
            if(nod > i)
                sfx.add(i, nod);
    sfx.DFS(0);

    int Q = L.size();
    vector<int> ans;
    ans.resize(Q);
    vector<pii> itv;
    itv.resize(Q + 2);
    vector< vector<int> > upd;
    upd.resize(N + 2);

    for(int i = 0; i < Q; i++)
    {
        int nod = S[i], lmt = L[i];
        for(int i = 18; i >= 0; i--)
            if(sfx.fth[i][nod] != -1 && sfx.fth[i][nod] >= lmt)
                nod = sfx.fth[i][nod];
        pii itvsfx = {sfx.lft[nod], sfx.rgt[nod]};

        nod = T[i], lmt = R[i];
        for(int i = 18; i >= 0; i--)
            if(pfx.fth[i][nod] != -1 && pfx.fth[i][nod] <= lmt)
                nod = pfx.fth[i][nod];
        pii itvpfx = {pfx.lft[nod], pfx.rgt[nod]};

        itv[i] = itvsfx;
        upd[itvpfx.first - 1].push_back( -(i + 1));
        upd[itvpfx.second].push_back(i + 1);
    }

    aib.init(N);
    for(int i = 1; i <= N; i++)
    {
        int nod = pfx.ord[i];
        aib.U(sfx.lft[nod], 1);

        for(auto id: upd[i])
        {
            int smn = 1;
            if(id < 0) smn = -1, id = -id;
            id--;

            ans[id] += smn * (aib.Q(itv[id].second) - aib.Q(itv[id].first - 1));
        }
    }

    for(int i = 0; i < Q; i++)
        if(ans[i] != 0) ans[i] = 1;
    return ans;
}

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:100:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < e1.size(); i++)
                    ~~^~~~~~~~~~~

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	400 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	508 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	380 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct

Subtask #2
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	400 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	508 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	380 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	8 ms	1784 KB	Output is correct
11	Correct	8 ms	1776 KB	Output is correct
12	Correct	7 ms	1656 KB	Output is correct
13	Correct	8 ms	1888 KB	Output is correct
14	Correct	8 ms	1784 KB	Output is correct
15	Correct	9 ms	1780 KB	Output is correct

Subtask #3
34.0 / 34.0

#	결과	실행 시간	메모리	Grader output
1	Correct	970 ms	95308 KB	Output is correct
2	Correct	1056 ms	96900 KB	Output is correct
3	Correct	809 ms	94728 KB	Output is correct
4	Correct	806 ms	93816 KB	Output is correct
5	Correct	794 ms	93856 KB	Output is correct
6	Correct	737 ms	94576 KB	Output is correct
7	Correct	722 ms	94124 KB	Output is correct
8	Correct	747 ms	96908 KB	Output is correct
9	Correct	550 ms	94756 KB	Output is correct
10	Correct	446 ms	93164 KB	Output is correct
11	Correct	505 ms	93432 KB	Output is correct
12	Correct	548 ms	93172 KB	Output is correct
13	Correct	897 ms	102072 KB	Output is correct
14	Correct	1094 ms	102232 KB	Output is correct
15	Correct	1108 ms	102204 KB	Output is correct
16	Correct	1012 ms	102168 KB	Output is correct
17	Correct	807 ms	93924 KB	Output is correct

Subtask #4
51.0 / 51.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	400 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	508 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	380 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	8 ms	1784 KB	Output is correct
11	Correct	8 ms	1776 KB	Output is correct
12	Correct	7 ms	1656 KB	Output is correct
13	Correct	8 ms	1888 KB	Output is correct
14	Correct	8 ms	1784 KB	Output is correct
15	Correct	9 ms	1780 KB	Output is correct
16	Correct	970 ms	95308 KB	Output is correct
17	Correct	1056 ms	96900 KB	Output is correct
18	Correct	809 ms	94728 KB	Output is correct
19	Correct	806 ms	93816 KB	Output is correct
20	Correct	794 ms	93856 KB	Output is correct
21	Correct	737 ms	94576 KB	Output is correct
22	Correct	722 ms	94124 KB	Output is correct
23	Correct	747 ms	96908 KB	Output is correct
24	Correct	550 ms	94756 KB	Output is correct
25	Correct	446 ms	93164 KB	Output is correct
26	Correct	505 ms	93432 KB	Output is correct
27	Correct	548 ms	93172 KB	Output is correct
28	Correct	897 ms	102072 KB	Output is correct
29	Correct	1094 ms	102232 KB	Output is correct
30	Correct	1108 ms	102204 KB	Output is correct
31	Correct	1012 ms	102168 KB	Output is correct
32	Correct	807 ms	93924 KB	Output is correct
33	Correct	1000 ms	95716 KB	Output is correct
34	Correct	319 ms	35076 KB	Output is correct
35	Correct	944 ms	97676 KB	Output is correct
36	Correct	794 ms	95736 KB	Output is correct
37	Correct	927 ms	97012 KB	Output is correct
38	Correct	956 ms	96280 KB	Output is correct
39	Correct	895 ms	102956 KB	Output is correct
40	Correct	892 ms	104188 KB	Output is correct
41	Correct	723 ms	95088 KB	Output is correct
42	Correct	633 ms	93944 KB	Output is correct
43	Correct	979 ms	101972 KB	Output is correct
44	Correct	889 ms	95732 KB	Output is correct
45	Correct	834 ms	104044 KB	Output is correct
46	Correct	803 ms	103732 KB	Output is correct
47	Correct	1134 ms	102344 KB	Output is correct
48	Correct	1014 ms	102332 KB	Output is correct
49	Correct	1036 ms	102516 KB	Output is correct
50	Correct	959 ms	102124 KB	Output is correct
51	Correct	846 ms	103288 KB	Output is correct
52	Correct	837 ms	103444 KB	Output is correct

답안 #96094

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 8.0 / 8.0

Subtask #3 34.0 / 34.0

Subtask #4 51.0 / 51.0

Subtask #1
7.0 / 7.0

Subtask #2
8.0 / 8.0

Subtask #3
34.0 / 34.0

Subtask #4
51.0 / 51.0