Submission #133482

#	Time	Username	Problem	Language	Result	Execution time	Memory
133482		thebes	늑대인간 (IOI18_werewolf)	C++14	100 / 100	1014 ms	103148 KiB

werewolf

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

const int MN = 4e5+5, LG = 20;
int ds[MN], p[MN], rep[MN], N, M, Q, i, j, vis[MN][2], nxt, sp[MN][LG], rev[MN], mp[MN], ans[MN];
struct edge{int x, y;}; vector<edge> ee;
vector<int> adj[MN];
int fnd(int x){return ds[x]=ds[x]==x?x:fnd(ds[x]);}
pair<int,int> a[MN]; set<int> st[MN];
struct qur{int s, r, id;}; vector<qur> q;

void dfs(int n){
    vis[n][0]=++nxt; rev[nxt]=n; mp[n]=nxt;
    sp[n][0]=p[n];
    for(auto v : adj[n])
        dfs(v);
    vis[n][1]=nxt;
}

int anc(int n,int h){
    for(int i=LG-1;i>=0;i--){
        if(sp[n][i]>=h) n=sp[n][i];
    }
    return n;
}

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(i=0;i<M;i++) ee.push_back({x[i]+1,y[i]+1});
    for(i=0;i<Q;i++) s[i]++,e[i]++,l[i]++,r[i]++;
    for(i=1;i<=N;i++) ds[i]=i,rep[i]=i;
    for(i=0;i<ee.size();i++){if(ee[i].x<ee[i].y)swap(ee[i].x,ee[i].y);}
    sort(ee.begin(),ee.end(),[](edge i,edge j){return i.y>j.y;});
    for(auto v : ee){
        if(fnd(v.x)!=fnd(v.y)){
            int x = fnd(v.x), y = fnd(v.y);
            if(rep[x]>rep[y]) swap(x,y);
            adj[rep[x]].push_back(rep[y]);
            ds[y] = x; p[y] = x;
        }
    }
    dfs(1);
    for(j=1;j<LG;j++){
        for(i=1;i<=N;i++)
            sp[i][j]=sp[sp[i][j-1]][j-1];
    }
    for(i=0;i<Q;i++){
        int x = anc(s[i], l[i]);
        a[i+1]={vis[x][0],vis[x][1]};
        q.push_back({e[i],r[i],i+1});
    }
    sort(q.begin(),q.end(),[](qur i,qur j){return i.r<j.r;});
    for(i=1;i<=N;i++) ds[i]=i,st[i].insert(i);
    for(i=0;i<ee.size();i++) swap(ee[i].x,ee[i].y);
    sort(ee.begin(),ee.end(),[](edge i,edge j){return i.y<j.y;});
    i = 0;
    for(auto v : ee){
        while(i<q.size()&&q[i].r<v.y){
            int x = fnd(mp[q[i].s]);
            int id = q[i].id;
            auto it = st[x].lower_bound(a[id].first);
            if(it!=st[x].end()&&*it<=a[id].second) ans[id]=1;
            i++;
        }
        if(fnd(mp[v.x])!=fnd(mp[v.y])){
            int x = fnd(mp[v.x]), y = fnd(mp[v.y]);
            if(st[x].size()>st[y].size()) swap(x,y);
            for(auto v : st[x]) st[y].insert(v);
            st[x].clear();
            ds[x] = y;
        }
    }
    while(i<q.size()){
        int x = fnd(q[i].s);
        int id = q[i].id;
        auto it = st[x].lower_bound(a[id].first);
        if(it!=st[x].end()&&*it<=a[id].second) ans[id]=1;
        i++;
    }
    vector<int> res;
    for(i=1;i<=Q;i++) res.push_back(ans[i]);
    return res;
}

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:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<ee.size();i++){if(ee[i].x<ee[i].y)swap(ee[i].x,ee[i].y);}
             ~^~~~~~~~~~
werewolf.cpp:54:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<ee.size();i++) swap(ee[i].x,ee[i].y);
             ~^~~~~~~~~~
werewolf.cpp:58:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(i<q.size()&&q[i].r<v.y){
               ~^~~~~~~~~
werewolf.cpp:73:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(i<q.size()){
           ~^~~~~~~~~

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