oj.uz

Submission #1003518

# Submission time Handle Problem Language Result Execution time Memory
1003518 2024-06-20T12:14:09 Z andrei_iorgulescu Werewolf (IOI18_werewolf) C++14
15 / 100
 1717 ms 524288 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];
map<pair<int,int>, vector<pair<int,int>>> huh;

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}});
        }
        if (valori[i].size() >= 20)
            while (true);
        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;
    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),huh[{x,it.first}].push_back(it.second);
            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 11 ms 23900 KB Output is correct
2 Correct 10 ms 23932 KB Output is correct
3 Correct 12 ms 23900 KB Output is correct
4 Correct 9 ms 23876 KB Output is correct
5 Correct 12 ms 23964 KB Output is correct
6 Correct 10 ms 23900 KB Output is correct
7 Correct 10 ms 23956 KB Output is correct
8 Correct 10 ms 23900 KB Output is correct
9 Correct 10 ms 23896 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23900 KB Output is correct
2 Correct 10 ms 23932 KB Output is correct
3 Correct 12 ms 23900 KB Output is correct
4 Correct 9 ms 23876 KB Output is correct
5 Correct 12 ms 23964 KB Output is correct
6 Correct 10 ms 23900 KB Output is correct
7 Correct 10 ms 23956 KB Output is correct
8 Correct 10 ms 23900 KB Output is correct
9 Correct 10 ms 23896 KB Output is correct
10 Correct 21 ms 26852 KB Output is correct
11 Correct 20 ms 26972 KB Output is correct
12 Correct 25 ms 29532 KB Output is correct
13 Correct 20 ms 26456 KB Output is correct
14 Correct 18 ms 26972 KB Output is correct
15 Correct 19 ms 27228 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 1717 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23900 KB Output is correct
2 Correct 10 ms 23932 KB Output is correct
3 Correct 12 ms 23900 KB Output is correct
4 Correct 9 ms 23876 KB Output is correct
5 Correct 12 ms 23964 KB Output is correct
6 Correct 10 ms 23900 KB Output is correct
7 Correct 10 ms 23956 KB Output is correct
8 Correct 10 ms 23900 KB Output is correct
9 Correct 10 ms 23896 KB Output is correct
10 Correct 21 ms 26852 KB Output is correct
11 Correct 20 ms 26972 KB Output is correct
12 Correct 25 ms 29532 KB Output is correct
13 Correct 20 ms 26456 KB Output is correct
14 Correct 18 ms 26972 KB Output is correct
15 Correct 19 ms 27228 KB Output is correct
16 Runtime error 1717 ms 524288 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -