oj.uz

Submission #1003513

# Submission time Handle Problem Language Result Execution time Memory
1003513 2024-06-20T12:11:02 Z andrei_iorgulescu Werewolf (IOI18_werewolf) C++14
15 / 100
 1184 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<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;
    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 17 ms 33372 KB Output is correct
2 Correct 15 ms 33372 KB Output is correct
3 Correct 12 ms 33328 KB Output is correct
4 Correct 12 ms 33112 KB Output is correct
5 Correct 13 ms 33372 KB Output is correct
6 Correct 13 ms 33276 KB Output is correct
7 Correct 12 ms 33624 KB Output is correct
8 Correct 14 ms 33372 KB Output is correct
9 Correct 14 ms 33404 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 33372 KB Output is correct
2 Correct 15 ms 33372 KB Output is correct
3 Correct 12 ms 33328 KB Output is correct
4 Correct 12 ms 33112 KB Output is correct
5 Correct 13 ms 33372 KB Output is correct
6 Correct 13 ms 33276 KB Output is correct
7 Correct 12 ms 33624 KB Output is correct
8 Correct 14 ms 33372 KB Output is correct
9 Correct 14 ms 33404 KB Output is correct
10 Correct 24 ms 36180 KB Output is correct
11 Correct 22 ms 36444 KB Output is correct
12 Correct 26 ms 39084 KB Output is correct
13 Correct 22 ms 35708 KB Output is correct
14 Correct 20 ms 36572 KB Output is correct
15 Correct 22 ms 36444 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 1184 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 17 ms 33372 KB Output is correct
2 Correct 15 ms 33372 KB Output is correct
3 Correct 12 ms 33328 KB Output is correct
4 Correct 12 ms 33112 KB Output is correct
5 Correct 13 ms 33372 KB Output is correct
6 Correct 13 ms 33276 KB Output is correct
7 Correct 12 ms 33624 KB Output is correct
8 Correct 14 ms 33372 KB Output is correct
9 Correct 14 ms 33404 KB Output is correct
10 Correct 24 ms 36180 KB Output is correct
11 Correct 22 ms 36444 KB Output is correct
12 Correct 26 ms 39084 KB Output is correct
13 Correct 22 ms 35708 KB Output is correct
14 Correct 20 ms 36572 KB Output is correct
15 Correct 22 ms 36444 KB Output is correct
16 Runtime error 1184 ms 524288 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -