oj.uz

Submission #1003525

# Submission time Handle Problem Language Result Execution time Memory
1003525 2024-06-20T12:19:09 Z andrei_iorgulescu Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 441340 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] and itt.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 14 ms 34944 KB Output is correct
3 Correct 13 ms 34904 KB Output is correct
4 Correct 14 ms 34648 KB Output is correct
5 Correct 14 ms 34908 KB Output is correct
6 Correct 13 ms 34908 KB Output is correct
7 Correct 15 ms 34904 KB Output is correct
8 Correct 13 ms 34908 KB Output is correct
9 Correct 12 ms 34936 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 14 ms 34944 KB Output is correct
3 Correct 13 ms 34904 KB Output is correct
4 Correct 14 ms 34648 KB Output is correct
5 Correct 14 ms 34908 KB Output is correct
6 Correct 13 ms 34908 KB Output is correct
7 Correct 15 ms 34904 KB Output is correct
8 Correct 13 ms 34908 KB Output is correct
9 Correct 12 ms 34936 KB Output is correct
10 Correct 23 ms 37208 KB Output is correct
11 Correct 22 ms 37360 KB Output is correct
12 Correct 23 ms 38996 KB Output is correct
13 Correct 20 ms 36696 KB Output is correct
14 Correct 20 ms 37012 KB Output is correct
15 Correct 31 ms 37724 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 2142 ms 441340 KB Output is correct
2 Execution timed out 4062 ms 171580 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 14 ms 34944 KB Output is correct
3 Correct 13 ms 34904 KB Output is correct
4 Correct 14 ms 34648 KB Output is correct
5 Correct 14 ms 34908 KB Output is correct
6 Correct 13 ms 34908 KB Output is correct
7 Correct 15 ms 34904 KB Output is correct
8 Correct 13 ms 34908 KB Output is correct
9 Correct 12 ms 34936 KB Output is correct
10 Correct 23 ms 37208 KB Output is correct
11 Correct 22 ms 37360 KB Output is correct
12 Correct 23 ms 38996 KB Output is correct
13 Correct 20 ms 36696 KB Output is correct
14 Correct 20 ms 37012 KB Output is correct
15 Correct 31 ms 37724 KB Output is correct
16 Correct 2142 ms 441340 KB Output is correct
17 Execution timed out 4062 ms 171580 KB Time limit exceeded
18 Halted 0 ms 0 KB -