oj.uz

Submission #1003526

# Submission time Handle Problem Language Result Execution time Memory
1003526 2024-06-20T12:20:01 Z andrei_iorgulescu Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 445604 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, vector<pair<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])
            huh[i][it.first].push_back(it.second);
    }
    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),huh[x][it.first].push_back(it.second);
            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
            for (auto itt : huh[x][cine])
                if (itt.first <= R[it])
                    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 14 ms 34904 KB Output is correct
2 Correct 14 ms 34904 KB Output is correct
3 Correct 14 ms 34908 KB Output is correct
4 Correct 14 ms 34652 KB Output is correct
5 Correct 14 ms 34908 KB Output is correct
6 Correct 14 ms 34904 KB Output is correct
7 Correct 15 ms 34884 KB Output is correct
8 Correct 20 ms 34908 KB Output is correct
9 Correct 14 ms 34908 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 34904 KB Output is correct
2 Correct 14 ms 34904 KB Output is correct
3 Correct 14 ms 34908 KB Output is correct
4 Correct 14 ms 34652 KB Output is correct
5 Correct 14 ms 34908 KB Output is correct
6 Correct 14 ms 34904 KB Output is correct
7 Correct 15 ms 34884 KB Output is correct
8 Correct 20 ms 34908 KB Output is correct
9 Correct 14 ms 34908 KB Output is correct
10 Correct 22 ms 37044 KB Output is correct
11 Correct 22 ms 37468 KB Output is correct
12 Correct 24 ms 38996 KB Output is correct
13 Correct 22 ms 36696 KB Output is correct
14 Correct 20 ms 37208 KB Output is correct
15 Correct 22 ms 37724 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1982 ms 445604 KB Output is correct
2 Execution timed out 4064 ms 172604 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 34904 KB Output is correct
2 Correct 14 ms 34904 KB Output is correct
3 Correct 14 ms 34908 KB Output is correct
4 Correct 14 ms 34652 KB Output is correct
5 Correct 14 ms 34908 KB Output is correct
6 Correct 14 ms 34904 KB Output is correct
7 Correct 15 ms 34884 KB Output is correct
8 Correct 20 ms 34908 KB Output is correct
9 Correct 14 ms 34908 KB Output is correct
10 Correct 22 ms 37044 KB Output is correct
11 Correct 22 ms 37468 KB Output is correct
12 Correct 24 ms 38996 KB Output is correct
13 Correct 22 ms 36696 KB Output is correct
14 Correct 20 ms 37208 KB Output is correct
15 Correct 22 ms 37724 KB Output is correct
16 Correct 1982 ms 445604 KB Output is correct
17 Execution timed out 4064 ms 172604 KB Time limit exceeded
18 Halted 0 ms 0 KB -