Submission #1245140

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245140		DeathIsAwe	Werewolf (IOI18_werewolf)	C++20	15 / 100	4091 ms	71184 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define ld long double
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
vector<vector<int>> graph;
int smallest[3000][3000], largest[3000][3000];
int m, q;


vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r) {
    m = x.size();
    q = s.size();
    vector<int> dum;
    for (int i=0;i<n;i++) graph.pb(dum);
    for (int i=0;i<m;i++) {
        graph[x[i]].pb(y[i]);
        graph[y[i]].pb(x[i]);
    }


    vector<bool> visited(n);
    for (int i=0;i<n;i++) {
        for (int j=0;j<n;j++) visited[j] = false;
        smallest[i][i] = i;
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
        pq.push(mp(i, i));
        while (pq.size() > 0) {
            pair<int,int> node = pq.top(); pq.pop();
            if (visited[node.ss]) continue;
            visited[node.ss] = true;
            for (int j: graph[node.ss]) {
                if (!visited[j]) {
                    smallest[i][j] = max(node.ff, j);
                    pq.push(mp(smallest[i][j], j));
                }
            }
        }
    }
    for (int i=0;i<n;i++) {
        for (int j=0;j<n;j++) visited[j] = false;
        largest[i][i] = i;
        priority_queue<pair<int,int>> pq;
        pq.push(mp(i, i));
        while (pq.size() > 0) {
            pair<int,int> node = pq.top(); pq.pop();
            if (visited[node.ss]) continue;
            visited[node.ss] = true;
            for (int j: graph[node.ss]) {
                if (!visited[j]) {
                    largest[i][j] = min(node.ff, j);
                    pq.push(mp(largest[i][j], j));
                }
            }
        }
    }


    vector<int> ansvec;
    for (int i=0;i<q;i++) {
        bool flag = false;
        for (int j=0;j<n;j++) {
            if (largest[s[i]][j] >= l[i] && smallest[e[i]][j] <= r[i] && j >= l[i] && j <= r[i]) {
                flag = true;
                ansvec.pb(1);
                break;
            }
        }
        if (!flag) {
            ansvec.pb(0);
        }
    }
    return ansvec;
}   

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51