oj.uz

Submission #318643

# Submission time Handle Problem Language Result Execution time Memory
318643 2020-11-02T15:51:18 Z ivan_tudor Werewolf (IOI18_werewolf) C++14
100 / 100
 1106 ms 111744 KB 
#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 200005;
vector<int> gr[N];
vector<int> amin[N], amax[N];
int dmin[20][N], dmax[20][N];
int pmin[N], pmax[N];
int findt(int x, int p[]){
  if(x == p[x])
    return x;
  p[x] = findt(p[x], p);
  return p[x];
}
void join (int x, int y, int p[], int d[20][N]){ // x tatal de care unesc pe fiul y
  if(findt(x,p) != findt(y,p)){
    y = findt(y,p);
    p[y] = x;
    d[0][y] = x;
  }
}

struct intv{
  int l,r;
};
intv itvmin[N];
int postord[N];
void dfsmin(int nod,int dad, int &cnt){
  cnt++;
  itvmin[nod].l = cnt;
  postord[cnt] = nod;
  for(auto x: amin[nod]){
    if(x!=dad){
      dfsmin(x,nod,cnt);
    }
  }
  itvmin[nod].r = cnt;
}

intv itvmax[N];
void dfsmax(int nod,int dad, int &cnt){
  cnt++;
  itvmax[nod].l = cnt;
  for(auto x: amax[nod]){
    if(x!=dad){
      dfsmax(x,nod,cnt);
    }
  }
  itvmax[nod].r = cnt;
}

struct querys{
  int l;
  int c1,c2;
  int type;
  int id;
};
bool cmpquerys(querys a, querys b){
  return a.l < b.l;
}

int aib[N];
void update(int poz,int val){
  for(int i = poz; i < N ; i+= i&(-i))
    aib[i] += val;
}
int query(int poz){
  int ans = 0;
  for(int i=poz; i>0; i-= i&(-i))
    ans+=aib[i];
  return ans;
}

std::vector<int> check_validity(int n, vector<int> X, vector<int> Y,vector<int> S, vector<int> E,vector<int> L, vector<int> R) {
  for(int i = 0; i< X.size(); i++){
    gr[X[i] + 1].push_back(Y[i] + 1);
    gr[Y[i] + 1].push_back(X[i] + 1);
  }
  for(int i=1;i<=n;i++){
    pmin[i] = pmax[i] = i;
  }
  for(int i=1; i<=n;i++){
    for(auto j:gr[i]){
      if(j < i){
        join(i, j, pmax, dmax);
      }
    }
  }
  for(int i=1; i<=n; i++){
    amax[dmax[0][i]].push_back(i);
    amax[i].push_back(dmax[0][i]);
  }
  int cnt = 0;
  dfsmax(n, 0, cnt);
  for(int i = n; i>=1; i--){
    for(auto j:gr[i]){
      if(j > i){
        join(i, j, pmin, dmin);
      }
    }
  }
  cnt = 0;
  for(int i=1; i<=n; i++){
    amin[dmin[0][i]].push_back(i);
    amin[i].push_back(dmin[0][i]);
  }
  dfsmin(1, 0, cnt);
  for(int log = 1; log < 20; log ++){
    for(int i= 1; i<=n;i++){
      dmin[log][i] = dmin[log-1][dmin[log-1][i]];
      dmax[log][i] = dmax[log-1][dmax[log-1][i]];
    }
  }
  int Q = S.size();
  vector<querys> q;
  for(int i = 0 ; i < Q ; i++){
    int s = S[i] + 1;
    int e = E[i] + 1;
    int l = L[i] + 1;
    int r = R[i] + 1;

    for(int pas = 19; pas >= 0; pas--){
      if(dmin[pas][s]!=0 && dmin[pas][s] >= l)
        s = dmin[pas][s];
    }
    intv mn = itvmin[s];
    for(int pas = 19; pas>=0; pas--){
      if(dmax[pas][e]!=0 && dmax[pas][e] <= r)
        e = dmax[pas][e];
    }
    intv mx = itvmax[e];
    q.push_back({mn.l-1, mx.l, mx.r, -1, i});
    q.push_back({mn.r, mx.l, mx.r, 1, i});
  }
  std::vector<int> A(Q);
  sort(q.begin(),q.end(),cmpquerys);
  int pc = 1;
  for(auto qc:q){
    while(pc <= qc.l){
      update(itvmax[postord[pc]].l, 1);
      pc++;
    }
    A[qc.id] += qc.type * (query(qc.c2) - query(qc.c1 - 1));
  }
  for(auto &a: A)
    if(a > 0)
      a = 1;
    else
      a = 0;
  return A;
}

Compilation message

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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14700 KB Output is correct
2 Correct 10 ms 14700 KB Output is correct
3 Correct 9 ms 14700 KB Output is correct
4 Correct 10 ms 14700 KB Output is correct
5 Correct 10 ms 14700 KB Output is correct
6 Correct 10 ms 14700 KB Output is correct
7 Correct 12 ms 14700 KB Output is correct
8 Correct 11 ms 14700 KB Output is correct
9 Correct 10 ms 14720 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14700 KB Output is correct
2 Correct 10 ms 14700 KB Output is correct
3 Correct 9 ms 14700 KB Output is correct
4 Correct 10 ms 14700 KB Output is correct
5 Correct 10 ms 14700 KB Output is correct
6 Correct 10 ms 14700 KB Output is correct
7 Correct 12 ms 14700 KB Output is correct
8 Correct 11 ms 14700 KB Output is correct
9 Correct 10 ms 14720 KB Output is correct
10 Correct 16 ms 16108 KB Output is correct
11 Correct 17 ms 16080 KB Output is correct
12 Correct 16 ms 16076 KB Output is correct
13 Correct 16 ms 16236 KB Output is correct
14 Correct 16 ms 16236 KB Output is correct
15 Correct 17 ms 16204 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1024 ms 98384 KB Output is correct
2 Correct 987 ms 102984 KB Output is correct
3 Correct 977 ms 99928 KB Output is correct
4 Correct 912 ms 98672 KB Output is correct
5 Correct 904 ms 98508 KB Output is correct
6 Correct 978 ms 98372 KB Output is correct
7 Correct 989 ms 98380 KB Output is correct
8 Correct 855 ms 102860 KB Output is correct
9 Correct 604 ms 99916 KB Output is correct
10 Correct 505 ms 98640 KB Output is correct
11 Correct 551 ms 98504 KB Output is correct
12 Correct 556 ms 98376 KB Output is correct
13 Correct 1000 ms 104700 KB Output is correct
14 Correct 1000 ms 104704 KB Output is correct
15 Correct 1018 ms 104780 KB Output is correct
16 Correct 1014 ms 104660 KB Output is correct
17 Correct 995 ms 98384 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14700 KB Output is correct
2 Correct 10 ms 14700 KB Output is correct
3 Correct 9 ms 14700 KB Output is correct
4 Correct 10 ms 14700 KB Output is correct
5 Correct 10 ms 14700 KB Output is correct
6 Correct 10 ms 14700 KB Output is correct
7 Correct 12 ms 14700 KB Output is correct
8 Correct 11 ms 14700 KB Output is correct
9 Correct 10 ms 14720 KB Output is correct
10 Correct 16 ms 16108 KB Output is correct
11 Correct 17 ms 16080 KB Output is correct
12 Correct 16 ms 16076 KB Output is correct
13 Correct 16 ms 16236 KB Output is correct
14 Correct 16 ms 16236 KB Output is correct
15 Correct 17 ms 16204 KB Output is correct
16 Correct 1024 ms 98384 KB Output is correct
17 Correct 987 ms 102984 KB Output is correct
18 Correct 977 ms 99928 KB Output is correct
19 Correct 912 ms 98672 KB Output is correct
20 Correct 904 ms 98508 KB Output is correct
21 Correct 978 ms 98372 KB Output is correct
22 Correct 989 ms 98380 KB Output is correct
23 Correct 855 ms 102860 KB Output is correct
24 Correct 604 ms 99916 KB Output is correct
25 Correct 505 ms 98640 KB Output is correct
26 Correct 551 ms 98504 KB Output is correct
27 Correct 556 ms 98376 KB Output is correct
28 Correct 1000 ms 104700 KB Output is correct
29 Correct 1000 ms 104704 KB Output is correct
30 Correct 1018 ms 104780 KB Output is correct
31 Correct 1014 ms 104660 KB Output is correct
32 Correct 995 ms 98384 KB Output is correct
33 Correct 1037 ms 99856 KB Output is correct
34 Correct 393 ms 56020 KB Output is correct
35 Correct 1106 ms 103008 KB Output is correct
36 Correct 999 ms 99144 KB Output is correct
37 Correct 1064 ms 102104 KB Output is correct
38 Correct 1014 ms 99844 KB Output is correct
39 Correct 990 ms 111308 KB Output is correct
40 Correct 1083 ms 108536 KB Output is correct
41 Correct 754 ms 101452 KB Output is correct
42 Correct 594 ms 99172 KB Output is correct
43 Correct 1032 ms 107336 KB Output is correct
44 Correct 903 ms 101960 KB Output is correct
45 Correct 712 ms 111744 KB Output is correct
46 Correct 728 ms 111476 KB Output is correct
47 Correct 984 ms 104780 KB Output is correct
48 Correct 991 ms 104720 KB Output is correct
49 Correct 980 ms 104832 KB Output is correct
50 Correct 990 ms 104524 KB Output is correct
51 Correct 882 ms 109000 KB Output is correct
52 Correct 874 ms 109028 KB Output is correct