oj.uz

Submission #1003528

# Submission time Handle Problem Language Result Execution time Memory
1003528 2024-06-20T12:23:57 Z andrei_iorgulescu Werewolf (IOI18_werewolf) C++14
100 / 100
 1461 ms 374156 KB 
#include <bits/stdc++.h>
#include "werewolf.h"

using namespace std;

int n,m,q;
vector<pair<int,int>> id_changes[200005];///pentru R incepand cu .first, am id-ul .second
vector<pair<int,pair<int,int>>> valori[200005], valori0[200005];
vector<int> fii[200005];
int t[200005];
vector<int> queries[200005];
unordered_map<int,int> huh[200005];

int get_id(int cine,int mom)
{
    for (auto it : valori0[cine])
        if (it.second.first <= mom and it.second.second >= mom)
            return it.first;
    return -1;
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R)
{
    n = N;
    m = X.size();
    q = S.size();
    for (int i = 0; i < m; i++)
        X[i]++,Y[i]++;
    for (int i = 0; i < q; i++)
        S[i]++,E[i]++,L[i]++,R[i]++;
    for (int i = 1; i <= n; i++)
        id_changes[i].push_back({i,i});
    for (int i = 1; i <= n; i++)
        t[i] = i,fii[i].push_back(i);
    vector<pair<int,pair<int,int>>> e_wolf;
    for (int i = 0; i < m; i++)
        e_wolf.push_back({max(X[i],Y[i]),{X[i],Y[i]}});
    sort(e_wolf.begin(),e_wolf.end());
    for (auto it : e_wolf)
    {
        int x = it.second.first,y = it.second.second;
        int mom = it.first;
        if (t[x] == t[y])
            continue;
        x = t[x],y = t[y];
        if (fii[x].size() < fii[y].size())
            swap(x,y);
        for (auto it : fii[y])
        {
            t[it] = x;
            fii[x].push_back(it);
            id_changes[it].push_back({mom,x});
        }
        fii[y].clear();
    }
    for (int i = 1; i <= n; i++)
        fii[i].clear();
    for (int i = 1; i <= n; i++)
    {
        t[i] = i;
        fii[i].push_back(i);
        for (int j = 0; j < id_changes[i].size(); j++)
        {
            if(j + 1 != id_changes[i].size() and id_changes[i][j] != id_changes[i][j + 1])
                valori[i].push_back({id_changes[i][j].second,{id_changes[i][j].first,id_changes[i][j + 1].first - 1}});
            else if (j + 1 == id_changes[i].size())
                valori[i].push_back({id_changes[i][j].second,{id_changes[i][j].first,n}});
        }
        valori0[i] = valori[i];
        for (auto it : valori[i])
        {
            if (huh[i][it.first] == 0 or huh[i][it.first] >= it.second.first)
                huh[i][it.first] = it.second.first;
        }
    }
    vector<pair<int,pair<int,int>>> e_om;
    for (int i = 0; i < m; i++)
        e_om.push_back({min(X[i],Y[i]),{X[i],Y[i]}});
    sort(e_om.begin(),e_om.end());
    reverse(e_om.begin(),e_om.end());
    for (int i = 0; i < q; i++)
        queries[L[i]].push_back(i);
    vector<int> answer(q);
    int i1 = 0;
    vector<int> treceri(n + 1);
    for (int l = n; l >= 1; l--)
    {
        while (i1 < m and e_om[i1].first >= l)
        {
            int x = e_om[i1].second.first,y = e_om[i1].second.second;
            i1++;
            ///unesc cu muchia x--y
            if (t[x] == t[y])
                continue;
            x = t[x],y = t[y];
            if (fii[x].size() < fii[y].size())
                swap(x,y);
            for (auto it : fii[y])
            {
                t[it] = x;
                fii[x].push_back(it);
                treceri[it]++;
                if (treceri[it] >= 20)
                    assert(false);
            }
            for (auto it : valori[y])
            {
                valori[x].push_back(it);
                if (huh[x][it.first] == 0 or huh[x][it.first] > it.second.first)
                    huh[x][it.first] = it.second.first;
            }
            huh[y].clear();
            fii[y].clear();
            valori[y].clear();
        }
        for (auto it : queries[l])
        {
            int x = t[S[it]];
            int cine = get_id(E[it],R[it]);
            ///daca am, in setul de valori ale lui x, pe id-ul cine cu interval care contine R[it], e bine
                if (huh[x][cine] <= R[it] and huh[x][cine] != 0)
                    answer[it] = 1;
        }
    }
    return answer;
}

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:62:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for (int j = 0; j < id_changes[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             if(j + 1 != id_changes[i].size() and id_changes[i][j] != id_changes[i][j + 1])
      |                ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:66:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             else if (j + 1 == id_changes[i].size())
      |                      ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 34904 KB Output is correct
2 Correct 14 ms 34908 KB Output is correct
3 Correct 14 ms 34752 KB Output is correct
4 Correct 15 ms 34648 KB Output is correct
5 Correct 17 ms 34904 KB Output is correct
6 Correct 15 ms 34908 KB Output is correct
7 Correct 14 ms 34908 KB Output is correct
8 Correct 14 ms 34908 KB Output is correct
9 Correct 14 ms 34852 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 34904 KB Output is correct
2 Correct 14 ms 34908 KB Output is correct
3 Correct 14 ms 34752 KB Output is correct
4 Correct 15 ms 34648 KB Output is correct
5 Correct 17 ms 34904 KB Output is correct
6 Correct 15 ms 34908 KB Output is correct
7 Correct 14 ms 34908 KB Output is correct
8 Correct 14 ms 34908 KB Output is correct
9 Correct 14 ms 34852 KB Output is correct
10 Correct 19 ms 36696 KB Output is correct
11 Correct 19 ms 36952 KB Output is correct
12 Correct 22 ms 38188 KB Output is correct
13 Correct 19 ms 36384 KB Output is correct
14 Correct 20 ms 36696 KB Output is correct
15 Correct 23 ms 36952 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1461 ms 364752 KB Output is correct
2 Correct 521 ms 156400 KB Output is correct
3 Correct 599 ms 188192 KB Output is correct
4 Correct 776 ms 233840 KB Output is correct
5 Correct 853 ms 243292 KB Output is correct
6 Correct 1222 ms 279112 KB Output is correct
7 Correct 1341 ms 374156 KB Output is correct
8 Correct 463 ms 156472 KB Output is correct
9 Correct 527 ms 185948 KB Output is correct
10 Correct 748 ms 234276 KB Output is correct
11 Correct 795 ms 241196 KB Output is correct
12 Correct 1064 ms 280400 KB Output is correct
13 Correct 463 ms 152004 KB Output is correct
14 Correct 476 ms 153892 KB Output is correct
15 Correct 461 ms 152200 KB Output is correct
16 Correct 478 ms 152188 KB Output is correct
17 Correct 1317 ms 366804 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 34904 KB Output is correct
2 Correct 14 ms 34908 KB Output is correct
3 Correct 14 ms 34752 KB Output is correct
4 Correct 15 ms 34648 KB Output is correct
5 Correct 17 ms 34904 KB Output is correct
6 Correct 15 ms 34908 KB Output is correct
7 Correct 14 ms 34908 KB Output is correct
8 Correct 14 ms 34908 KB Output is correct
9 Correct 14 ms 34852 KB Output is correct
10 Correct 19 ms 36696 KB Output is correct
11 Correct 19 ms 36952 KB Output is correct
12 Correct 22 ms 38188 KB Output is correct
13 Correct 19 ms 36384 KB Output is correct
14 Correct 20 ms 36696 KB Output is correct
15 Correct 23 ms 36952 KB Output is correct
16 Correct 1461 ms 364752 KB Output is correct
17 Correct 521 ms 156400 KB Output is correct
18 Correct 599 ms 188192 KB Output is correct
19 Correct 776 ms 233840 KB Output is correct
20 Correct 853 ms 243292 KB Output is correct
21 Correct 1222 ms 279112 KB Output is correct
22 Correct 1341 ms 374156 KB Output is correct
23 Correct 463 ms 156472 KB Output is correct
24 Correct 527 ms 185948 KB Output is correct
25 Correct 748 ms 234276 KB Output is correct
26 Correct 795 ms 241196 KB Output is correct
27 Correct 1064 ms 280400 KB Output is correct
28 Correct 463 ms 152004 KB Output is correct
29 Correct 476 ms 153892 KB Output is correct
30 Correct 461 ms 152200 KB Output is correct
31 Correct 478 ms 152188 KB Output is correct
32 Correct 1317 ms 366804 KB Output is correct
33 Correct 894 ms 196408 KB Output is correct
34 Correct 223 ms 73148 KB Output is correct
35 Correct 689 ms 166924 KB Output is correct
36 Correct 967 ms 210988 KB Output is correct
37 Correct 715 ms 170040 KB Output is correct
38 Correct 879 ms 196920 KB Output is correct
39 Correct 696 ms 158780 KB Output is correct
40 Correct 670 ms 189696 KB Output is correct
41 Correct 676 ms 173724 KB Output is correct
42 Correct 780 ms 206636 KB Output is correct
43 Correct 566 ms 165928 KB Output is correct
44 Correct 669 ms 170804 KB Output is correct
45 Correct 548 ms 147488 KB Output is correct
46 Correct 612 ms 158200 KB Output is correct
47 Correct 460 ms 152216 KB Output is correct
48 Correct 476 ms 152372 KB Output is correct
49 Correct 442 ms 152384 KB Output is correct
50 Correct 452 ms 151940 KB Output is correct
51 Correct 692 ms 183140 KB Output is correct
52 Correct 716 ms 184672 KB Output is correct