Submission #727928

#	Time	Username	Problem	Language	Result	Execution time	Memory
727928		nguyentunglam	Werewolf (IOI18_werewolf)	C++17	100 / 100	1322 ms	206752 KiB

werewolf

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
#define ii pair<int, int>
using namespace std;

const int N = 6e5 + 10;
vector<ii> e1[N], e2[N];
int cnt;
vector<tuple<int, int, int, int> > query[N];

struct kruskal {
    int par[20][N], w[N], timer, lst[N];
    int st[N], ed[N];
    vector<int> ad[N];

    int root(int v) {
        return par[0][v] < 0 ? v : par[0][v] = root(par[0][v]);
    }

    void join(int u, int v, int c) {
        u = root(u); v = root(v);
        if (u == v) return;
        ++cnt;
        ad[cnt].push_back(u);
        ad[cnt].push_back(v);
        par[0][cnt] = -1; w[cnt] = c;
        par[0][u] = cnt; par[0][v] = cnt;
    }

    void dfs(int u) {
        st[u] = ++timer;
        lst[timer] = u;
        for(int j = 1; j <= 19; j++) {
            if (par[j - 1][u] < 0) par[j][u] = -1;
            else par[j][u] = par[j - 1][par[j - 1][u]];
        }
        for(int &v : ad[u]) {
            par[0][v] = u;
            dfs(v);
        }
        ed[u] = timer;
    }

    int get(int u, int cost, int type) {
        for(int j = 19; j >= 0; j--) {
            int p = par[j][u];
            if (p <= 0) continue;
            if (!type && w[p] <= cost) u = p;
            else if (type && w[p] >= cost) u = p;
        }
        return u;
    }

} T[2];

int bit[N];
void up(int pos, int val) {
    while (pos <= 6e5) {
        bit[pos] += val;
        pos += pos & -pos;
    }
}

int get(int pos) {
    int ret = 0;
    while (pos) {
        ret += bit[pos];
        pos -= pos & -pos;
    }
    return ret;
}

int getrange(int l, int r) {
    return get(r) - get(l - 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) {
    cnt = n - 1;

    for(int i = 0; i < x.size(); i++) {
        int u = x[i], v = y[i];
        e1[min(u, v)].emplace_back(u, v);
        e2[max(u, v)].emplace_back(u, v);
    }

    for(int i = 0; i < n; i++) T[0].par[0][i] = T[1].par[0][i] = -1;

    for(int i = 0; i < n; i++) for(auto &it : e2[i]) {
        T[0].join(it.fi, it.se, i);
    }
    for(int i = 0; i <= cnt; i++) if (T[0].par[0][i] < 0) T[0].dfs(i);
    for(int i = n - 1; i >= 0; i--) for(auto &it : e1[i]) {
        T[1].join(it.fi, it.se, i);
    }
    for(int i = 0; i <= cnt; i++) if (T[1].par[0][i] < 0) T[1].dfs(i);
    vector<int> ans;
    ans.resize(s.size());

    for(int i = 0; i < s.size(); i++) {
        int p1 = T[1].get(s[i], l[i], 1);
        int p2 = T[0].get(e[i], r[i], 0);
//        cout << p1 << " " << p2 << " " << T[0].w[p2] << " " << r[i] << endl;
        query[T[1].ed[p1]].emplace_back(T[0].st[p2], T[0].ed[p2], i, 1);
        query[T[1].st[p1] - 1].emplace_back(T[0].st[p2], T[0].ed[p2], i, -1);
    }

    for(int i = 0; i <= T[1].timer; i++) {
        int u = T[1].lst[i];
        if (u < n) up(T[0].st[u], 1);
        for(auto &it : query[i]) {
            int L, R, id, sign; tie(L, R, id, sign) = it;
            ans[id] += sign * getrange(L, R);
        }
    }

    for(int &i : ans) {
        i = (i > 0);
    }
    return ans;
}
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define pb push_back
#ifdef ngu
#define forv(a, b) for(auto &a : b)
int main() {
    #define task "task"
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);
    vector<int> x,y,st,ed,lf,rt;
    int n,m,q; cin>>n>>m>>q;
    forinc(i,1,m){
        x.pb(in),y.pb(in);
    }

    forinc(i,1,q){
        st.pb(in), ed.pb(in), lf.pb(in), rt.pb(in);
//        if (i == 82) cout << st.back() << " " << ed.back() << " " << lf.back() << " " << rt.back() << endl;
    }
    forv(i,check_validity(n,x,y,st,ed,lf,rt)) cout<<i<<"\n";
}
#endif // ngu

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

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