Submission #1122239

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122239		Luvidi	Werewolf (IOI18_werewolf)	C++17	0 / 100	484 ms	75532 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn=2e5;
vector<int> adj[maxn],ln;
int par[maxn],sm[maxn],lr[maxn],idx[maxn];
bool vis[maxn];

void dfs(int v){
    vis[v]=1;
    idx[v]=ln.size();
    ln.push_back(v);
    for(int u:adj[v])if(!vis[u])dfs(u);
}

int rep(int x){
    if(x==par[x])return x;
    return par[x]=rep(par[x]);
}

void join(int x,int y){
    x=rep(x);y=rep(y);
    par[x]=y;
    sm[y]=min(sm[y],sm[x]);
    lr[y]=max(lr[y],lr[x]);
}

std::vector<int> check_validity(int n, std::vector<int> x, std::vector<int> y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R) {
    for(int i=0;i<x.size();i++){
        adj[x[i]].push_back(y[i]);
        adj[y[i]].push_back(x[i]);
    }
    int en=0;
    while(adj[en].size()==2)en++;
    dfs(en);
    vector<int> s[n],e[n];
    for(int i=0;i<S.size();i++){
        s[L[i]].push_back(S[i]);
        e[R[i]].push_back(E[i]);
    }
    map<pair<int,int>,int> m1,m2;
    for(int i=0;i<n;i++){
        par[i]=i;
        lr[i]=idx[i];
    }
    for(int i=n-1;i>-1;i--){
        for(int j:adj[i])if(j>i)join(i,j);
        for(int x:s[i])m1[{i,x}]=lr[rep(x)];
    }
    for(int i=0;i<n;i++){
        par[i]=i;
        sm[i]=idx[i];
    }
    for(int i=0;i<n;i++){
        for(int j:adj[i])if(j<i)join(i,j);
        for(int x:e[i])m2[{i,x}]=sm[rep(x)];
    }
    vector<int> ans;
    for(int i=0;i<S.size();i++){
        int s=S[i],e=E[i],l=L[i],r=R[i];
        ans.push_back(m1[{l,s}]>=m2[{r,e}]);
    }
    return ans;
}

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:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i=0;i<x.size();i++){
      |                 ~^~~~~~~~~
werewolf.cpp:40:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i=0;i<S.size();i++){
      |                 ~^~~~~~~~~
werewolf.cpp:62:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i=0;i<S.size();i++){
      |                 ~^~~~~~~~~

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