Submission #1003512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003512		andrei_iorgulescu	Werewolf (IOI18_werewolf)	C++14	15 / 100	4026 ms	292576 KiB

werewolf

#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 (stderr)

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 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51