Submission #1011151

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011151		hyforces	늑대인간 (IOI18_werewolf)	C++14	100 / 100	344 ms	79444 KiB

werewolf

#include<bits/stdc++.h>
#include"werewolf.h"
using namespace std;
struct DSU{
    vector<int>fa;
    void init(int n){
        fa.resize(n);
        iota(fa.begin(),fa.end(),0);
    }
    int root(int u){return u==fa[u]?u:fa[u]=root(fa[u]);}
    bool merge(int u,int v){
        u=root(u),v=root(v);
        if(u==v)return false;
        fa[v]=u;
        return true;
    }
};
struct SegTree{
    int n;
    vector<int>t;
    void init(int n){
        this->n=n;
        t.clear();
        t.resize(2*n+2,0);
    }
    void add(int i,int v){
        for(t[i+=n]+=v;i>>=1;)t[i]=t[i<<1]+t[i<<1|1];
    }
    int query(int l,int r){
        int ret=0;
        for(l+=n,r+=n+1;l<r;l>>=1,r>>=1){
            if(l&1)ret+=t[l++];
            if(r&1)ret+=t[--r];
        }
        return ret;
    }
};
vector<vector<int>>fake1,fake2;
vector<int>tin1,tout1,ord1;
int t1=0;
void dfs1(int u){
    tin1[u]=++t1;
    ord1.push_back(u);
    for(auto a:fake1[u]){
        dfs1(a);
    }
    tout1[u]=t1;
}
vector<int>tin2,tout2,ord2;
int t2=0;
void dfs2(int u){
    tin2[u]=++t2;
    ord2.push_back(u);
    for(auto a:fake2[u]){
        dfs2(a);
    }
    tout2[u]=t2;
}

vector<int>check_validity(int n,vector<int>eu,vector<int>ev,vector<int>qs,vector<int>qe,vector<int>ql,vector<int>qr){
    int q=qs.size();
    vector<vector<int>>adj(n);
    for(int a=0;a<eu.size();++a){
        adj[eu[a]].push_back(ev[a]);
        adj[ev[a]].push_back(eu[a]);
    }
    fake1=fake2=vector<vector<int>>(n);
    DSU con;
    vector<int>qq(q);iota(qq.begin(),qq.end(),0);
    con.init(n);
    sort(qq.begin(),qq.end(),[&](int i,int j)->bool{
        return qr[i]<qr[j];
    });
    vector<int>qu(q),qv(q);
    for(int a=0,qa=0;a<n;++a){
        for(auto b:adj[a]){
            if(b>=a)continue;
            int ra=con.root(a),rb=con.root(b);
            if(ra!=rb){
                con.merge(ra,rb);
                fake1[ra].push_back(rb);
            }
        }
        while(qa<q&&qr[qq[qa]]<=a){
            qv[qq[qa]]=con.root(qe[qq[qa]]);
            ++qa;
        }
    }
    con.init(n);
    sort(qq.begin(),qq.end(),[&](int i,int j)->bool{
        return ql[i]>ql[j];
    });
    for(int a=n-1,qa=0;a>=0;--a){
        for(auto b:adj[a]){
            if(b<=a)continue;
            int ra=con.root(a),rb=con.root(b);
            if(ra!=rb){
                con.merge(ra,rb);
                fake2[ra].push_back(rb);
            }
        }
        while(qa<q&&ql[qq[qa]]>=a){
            qu[qq[qa]]=con.root(qs[qq[qa]]);
            ++qa;
        }
    }
    tin1.resize(n);tout1.resize(n);
    tin2.resize(n);tout2.resize(n);
    ord1.clear();
    ord2.clear();
    t1=t2=-1;
    dfs1(n-1);
    dfs2(0);
    vector<int>point(n);
    vector<vector<pair<int,bool>>>event(n+1);
    for(int a=0;a<n;++a)point[a]=tin2[ord1[a]];
    for(int a=0;a<q;++a){
        event[tin1[qv[a]]].push_back({a,true});
        event[tout1[qv[a]]+1].push_back({a,false});
    }
    SegTree pro;
    pro.init(n);
    vector<int>ans(q,0);
    for(int a=0;a<=n;++a){
        for(auto b:event[a]){
            if(b.second)ans[b.first]-=pro.query(tin2[qu[b.first]],tout2[qu[b.first]]);
            else ans[b.first]+=pro.query(tin2[qu[b.first]],tout2[qu[b.first]]);
        }
        if(a<n)pro.add(point[a],1);
    }
    for(auto&a:ans)a=(a>0);
    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:63:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int a=0;a<eu.size();++a){
      |                 ~^~~~~~~~~~

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