oj.uz

Submission #1003512

# Submission time Handle Problem Language Result Execution time Memory
1003512 2024-06-20T12:08:28 Z andrei_iorgulescu Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 292576 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,bool> am[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];
    }
    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;
    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);
            }
            for (auto it : valori[y])
                valori[x].push_back(it);
            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 : valori[x])
                if (itt.first == cine and itt.second.first <= R[it] and itt.second.second >= 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 34908 KB Output is correct
2 Correct 13 ms 34904 KB Output is correct
3 Correct 14 ms 34908 KB Output is correct
4 Correct 13 ms 34652 KB Output is correct
5 Correct 14 ms 34904 KB Output is correct
6 Correct 13 ms 34796 KB Output is correct
7 Correct 15 ms 34908 KB Output is correct
8 Correct 14 ms 34904 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 34908 KB Output is correct
2 Correct 13 ms 34904 KB Output is correct
3 Correct 14 ms 34908 KB Output is correct
4 Correct 13 ms 34652 KB Output is correct
5 Correct 14 ms 34904 KB Output is correct
6 Correct 13 ms 34796 KB Output is correct
7 Correct 15 ms 34908 KB Output is correct
8 Correct 14 ms 34904 KB Output is correct
9 Correct 14 ms 34908 KB Output is correct
10 Correct 31 ms 36184 KB Output is correct
11 Correct 25 ms 36116 KB Output is correct
12 Correct 19 ms 37232 KB Output is correct
13 Correct 23 ms 35932 KB Output is correct
14 Correct 17 ms 36188 KB Output is correct
15 Correct 24 ms 36696 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 762 ms 292576 KB Output is correct
2 Execution timed out 4026 ms 102984 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 34908 KB Output is correct
2 Correct 13 ms 34904 KB Output is correct
3 Correct 14 ms 34908 KB Output is correct
4 Correct 13 ms 34652 KB Output is correct
5 Correct 14 ms 34904 KB Output is correct
6 Correct 13 ms 34796 KB Output is correct
7 Correct 15 ms 34908 KB Output is correct
8 Correct 14 ms 34904 KB Output is correct
9 Correct 14 ms 34908 KB Output is correct
10 Correct 31 ms 36184 KB Output is correct
11 Correct 25 ms 36116 KB Output is correct
12 Correct 19 ms 37232 KB Output is correct
13 Correct 23 ms 35932 KB Output is correct
14 Correct 17 ms 36188 KB Output is correct
15 Correct 24 ms 36696 KB Output is correct
16 Correct 762 ms 292576 KB Output is correct
17 Execution timed out 4026 ms 102984 KB Time limit exceeded
18 Halted 0 ms 0 KB -