Submission #1171893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171893		Zero_OP	Werewolf (IOI18_werewolf)	C++20	Compilation error	0 ms	0 KiB

werewolf

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r)-1; i >= (l); --i)

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define compact(v) v.erase(unique(all(v)), end(v))

#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
      bool minimize(T& a, const T& b){
            if(a > b) return a = b, true;
            return false;
      }

template<typename T>
      bool maximize(T& a, const T& b){
            if(a < b) return a = b, true;
            return false;
      }

typedef long long ll;

using db = double;
using ull = unsigned long long;

using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;

using vi = vector<int>;
using vl = vector<ll>;
using vc = vector<char>;
using vd = vector<db>;
using vb = vector<bool>;

using vpi = vector<pi>;
using vpl = vector<pl>;

void setIO(){
      ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
      freopen("task.inp", "r", stdin);
      freopen("task.out", "w", stdout);
#endif
}

struct DSU_Tree{
      vi lab, tin, tout;
      int timer_dfs, used;
      vector<vi> adj;

      DSU_Tree(int n, int m){
          lab.resize(n+m, -1);
          tin.resize(n+m);
          tout.resize(n+m);
          adj.resize(n+m);
          timer_dfs = 0;
          used = n;
      }

      int root(int u){
            return lab[u] < 0 ? u : (lab[u] = root(lab[u]));
      }

      void join(int u, int v){
            u = root(u); v = root(v);
            adj[used].pb(u);
            if(u != v) adj[used].pb(v);

            lab[used] = lab[u] + lab[v];
            lab[u] = used; lab[v] = used;
            ++used;
      }

      void dfs(int u){
            tin[u] = ++timer_dfs;
            for(auto v : adj[u]){
                  dfs(v);
            }
            tout[u] = timer_dfs;
      }

      void process(){
            dfs(used-1);
      }
};

struct Fenwick{
      vi bit;
      Fenwick(int n) : bit(n + 1, 0) { }

      void update(int id, int val){
            for(; id < sz(bit); id += id & (-id)) bit[id] += val;
      }

      int query(int id){
            int sum = 0;
            for(; id > 0; id -= id & (-id)) sum += bit[id];
            return sum;
      }

      int query(int l, int r){
            return query(r) - query(l-1);
      }
};

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) {
      int Q = sz(S);
      int M = sz(X);

      vi result(Q, 1);

      vector<tuple<int, int, int>> events;
      FOR(i, 0, M){
            events.eb(min(X[i], Y[i]), X[i], Y[i]);
      }

      FOR(i, 0, Q){
            events.eb(L[i], -1, i);
      }

      sort(rall(events));

      vector<array<int, 2>> cover(Q, {-1, -1}), left(Q, {-1, -1}), right(Q, {-1, -1});
      vi x(N), y(N);

      DSU_Tree dsu(N, M);
      FOR(_, 0, sz(events)){
            int w, i, j; tie(w, i, j) = events[_];
            if(i == -1){ //query
                  int s = dsu.root(S[j]);
                  cover[j][0] = s;
            } else{ //edges
                  dsu.join(i, j);
            }
      }

      dsu.process();

      FOR(i, 0, Q){
            if(cover[i][0] != -1){
                  left[i][0] = dsu.tin[cover[i][0]];
                  right[i][0] = dsu.tout[cover[i][0]];
            }
      }

      FOR(i, 0, N) x[i] = dsu.tin[i];

      dsu = DSU_Tree(N, M);
      events.clear();


      FOR(i, 0, M){
            events.eb(max(X[i], Y[i]), X[i], Y[i]);
      }

      FOR(i, 0, Q) {
            events.eb(R[i], -1, i);
      }

      sort(all(events));

      FOR(_, 0, sz(events)){
            int w, i, j; tie(w, i, j) = events[_];
            if(i == -1){ //query
                  int e = dsu.root(E[j]);
                  cover[j][1] = e;
            } else{ //edges
                  dsu.join(i, j);
            }
      }

      dsu.process();

      FOR(i, 0, Q){
            if(cover[i][1] != -1){
                  left[i][1] = dsu.tin[cover[i][1]];
                  right[i][1] = dsu.tout[cover[i][1]];
            }
      }

      FOR(i, 0, N){
            y[i] = dsu.tin[i];
      }

      events.clear();
      vi cnt(Q);
      FOR(i, 0, Q){
            if(result[i]){
                  //can transform ?
                  events.eb(left[i][0]-1, 0, i);
                  events.eb(right[i][0], +1, i);
            }
      }

      FOR(i, 0, N) events.eb(x[i], -1, y[i]);

      sort(all(events));

      Fenwick BIT(N + M);
      FOR(_, 0, sz(events)){
            int x, type, y; tie(x, type, y) = events[_];
            if(type == -1) BIT.update(y, +1);
            else if(type == 0) cnt[y] -= BIT.query(left[y][1], right[y][1]);
            else cnt[y] += BIT.query(left[y][1], right[y][1]);
      }

      FOR(i, 0, Q){
          result[i] = cnt[i] > 0;
      }
      return result;
}

      int main(){
            ios_base::sync_with_stdio(0); cin.tie(0);

            int N, M, Q;
            cin >> N >> M >> Q;

            vi X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
            FOR(i, 0, M) cin >> X[i] >> Y[i];
            FOR(i, 0, Q) cin >> S[i] >> E[i] >> L[i] >> R[i];

            vi ans = check_validity(N, X, Y, S, E, L, R);
            FOR(i, 0, Q) cout << ans[i] << '\n';

            return 0;
      }

Compilation message (stderr)

/usr/bin/ld: /tmp/cc86ubxV.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc8STkQW.o:werewolf.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status