oj.uz

Submission #233729

# Submission time Handle Problem Language Result Execution time Memory
233729 2020-05-21T14:46:31 Z Theo830 Werewolf (IOI18_werewolf) C++17
15 / 100
 1174 ms 46584 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
//#include "werewolf.h"
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef int ll;
ll INF = 1e9+7;
long long MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define rf(i,a,b) for(ll i=a;i>=b;i--)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define w(t) while(t--)
#define c(n); cin>>n;
#define p(n) cout<<n;
#define pl(n) cout<<n<<"\n";
#define ps(n); cout<<n<<" ";
#define F first
#define S second
#define pb(a) push_back(a)
#define all(x) (x).begin(), (x).end()
#define ull unsigned long long
#define vll vector<ll>
#define vii vector<ii>
#define mkp make_pair
#define ld long double
#define arrin(a,n) f(i,0,n){cin>>a[i];}
#define arrout(a,n) f(i,0,n){cout<<a[i]<<" ";}
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
#define PI (2*acos(0))
const int N = 1e6+5;
vll visit,dist,taken,visit2;
vector<vll> adj,adj2;
priority_queue<ii,vector<ii>, greater<ii> > pq;
ll bit[1005][1005];
ll res = 0;
ll siz;
ll lcm(ll a,ll b){return (a * b) / __gcd(a,b);}
ll gcd(ll a,ll b){return __gcd(a,b);}
long long power(long long a,long long b){if(b == 0)return 1;if(b == 1)return a;long long ans = power(a,b/2) % MOD;ans *= ans;ans %= MOD;if(b % 2 == 1)ans *= a;return ans%MOD;}
ll inverse(ll x){x%=MOD;return power(x,MOD-2);}
void BITup(ll k, ll x,ll pos){while(k <= siz){bit[k][pos]+=x;k += k & -k;}}
ll BITq(ll k,ll pos){ll s=0;while(k>=1){s+=bit[k][pos];k -= k &-k;}return s;}
struct node{ll lazy,val,vali;}seg[800000];
struct point{ll x,y;};
void dfs(ll v){visit[v] = 1;for(auto x:adj[v]){if(!visit[x])dfs(x);}}
void dfs2(ll v){visit2[v] = 1;for(auto x:adj2[v]){if(!visit2[x])dfs2(x);}}
void bfs(ll s){visit[s] = 1;queue<ll>q;q.push(s);while(!q.empty()){ll u = q.front();ps(u);q.pop();for(auto x:adj[u]){if(!visit[x]){visit[x] = 1;q.push(x);}}}}
//void dijkstra(ll s){pq.push(ii(0,s));dist[s] = 0;while(!pq.empty()){ii f = pq.top();pq.pop();ll w = f.F;ll u = f.S;if(w > dist[u]){continue;}for(auto v:adj2[u]){if(dist[u] + v.S < dist[v.F]){dist[v.F] = dist[u] + v.S;pq.push(ii(dist[v.F],v.F));}}}}
//void prim(ll edge) {taken[edge] = 1;for(auto v:adj2[edge]) {if (taken[v.first]==0)pq.push(ii(v.second, v.first));}}
//ll mst(ll s){taken.assign(N, 0);prim(s);ll cost = 0;while(!pq.empty()){ii front = pq.top();pq.pop();ll w = front.first;ll u = front.second;if(taken[u]==0)cost += w;prim(u);}return cost;}
void YESNO(ll a){if(!!a){pl("YES");}else{pl("NO");}}
void filesin(void){freopen("tracing.in","r",stdin);}
void filesout(void){freopen("tracing.out","w",stdout);}
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Training
ll depth[N] = {0};
vll arr;
void ddfs(ll v){
    visit[v] = 1;
    arr[depth[v]] = v;
    for(auto x:adj[v]){
        if(!visit[x]){
            depth[x] = depth[v] + 1;
            ddfs(x);
        }
    }
}
bool ok1(ll x,ll y,ll l,ll r){
    if(x < l || y < l){
        return 0;
    }
    return 1;
}
bool ok2(ll x,ll y,ll l,ll r){
    if(x > r || y > r){
        return 0;
    }
    return 1;
}
void build(ll s,ll e,ll idx){
    if(s == e){
        seg[idx].val = seg[idx].vali = arr[s-1];
        return;
    }
    ll mid = (s+e)/2;
    build(s,mid,idx*2);
    build(mid+1,e,idx*2+1);
    seg[idx].val = min(seg[idx*2].val,seg[idx*2+1].val);
    seg[idx].vali = max(seg[idx*2].vali,seg[idx*2+1].vali);
}
ll query(ll s,ll e,ll qs,ll qe,ll idx){
    if(s >= qs && e <= qe){
        return seg[idx].val;
    }
    if(s > qe || e < qs){
        return INF;
    }
    ll mid = (s+e)/2;
    ll a = query(s,mid,qs,qe,idx*2);
    ll b = query(mid+1,e,qs,qe,idx*2+1);
    return min(a,b);
}
ll mquery(ll s,ll e,ll qs,ll qe,ll idx){
    if(s >= qs && e <= qe){
        return seg[idx].vali;
    }
    if(s > qe || e < qs){
        return -1;
    }
    ll mid = (s+e)/2;
    ll a = query(s,mid,qs,qe,idx*2);
    ll b = query(mid+1,e,qs,qe,idx*2+1);
    return max(a,b);
}
vector<int> check_validity(int n, vector<int> x,vector<int> y,vector<int> s,vector<int> e,vector<int> l, vector<int> r){
    int q = s.size();
    int m = x.size();
    vector<int>ans(q);
    if(q <= 3000 && m <= 6000){
        f(i,0,q){
            adj.assign(n+5,vll());
            adj2.assign(n+5,vll());
            f(j,0,m){
                if(ok1(x[j],y[j],l[i],r[i])){
                    adj[x[j]].pb(y[j]);
                    adj[y[j]].pb(x[j]);
                }
                if(ok2(x[j],y[j],l[i],r[i])){
                    adj2[x[j]].pb(y[j]);
                    adj2[y[j]].pb(x[j]);
                }
            }
            visit.assign(n+5,0);
            visit2.assign(n+5,0);
            dfs(s[i]);
            dfs2(e[i]);
            ans[i] = 0;
            f(j,l[i],r[i]+1){
                ans[i] = max(ans[i],(ll)(visit[j] == 1 && visit2[j] == 1));
            }
        }
    }
    else{
        vll arr;
        adj.assign(n+5,vll());
        f(i,0,m){
            adj[x[i]].pb(y[i]);
            adj[y[i]].pb(x[i]);
        }
        arr.assign(n,0);
        visit.assign(n+5,0);
        f(i,0,n){
            if(adj[i].size() == 1){
                ddfs(i);
                break;
            }
        }
        build(1,n,1);
        f(i,0,q){
            if(depth[s[i]] > depth[e[i]]){
                ll le = depth[e[i]],ri = depth[s[i]];
                ll ansi = INF;
                while(le <= ri){
                    ll mid = (le+ri)/2;
                    if(query(1,n,mid,depth[s[i]],1) >= l[i]){
                        ri = mid - 1;
                        ansi = min(ansi,mid);
                    }
                    else{
                        le = mid + 1;
                    }
                }
                if(ansi == INF){
                    ans[i] = 0;
                }
                else if(!(l[i] <= ansi && ansi <= r[i]) || !(ansi == depth[e[i]] || mquery(1,n,depth[e[i]],ansi-1,1) <= r[i])){
                    ans[i] = 0;
                }
                else{
                    ans[i] = 1;
                }
            }
            else{
                ll le = depth[s[i]],ri = depth[e[i]];
                ll ansi = -1;
                while(le <= ri){
                    ll mid = (le+ri)/2;
                    if(query(1,n,depth[s[i]],mid,1) >= l[i]){
                        le = mid + 1;
                        ansi = max(ansi,mid);
                    }
                    else{
                        ri = mid - 1;
                    }
                }
                if(ansi == -1){
                    ans[i] = 0;
                }
                else if(!(l[i] <= ansi && ansi <= r[i]) || (ansi == depth[e[i]] || mquery(1,n,ansi+1,depth[e[i]],1) <= r[i])){
                    ans[i] = 0;
                }
                else{
                    ans[i] = 1;
                }
            }
        }
    }
    return ans;
}
/*
namespace {

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace

int main() {
  int N = read_int();
  int M = read_int();
  int Q = read_int();
  std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
  for (int j = 0; j < M; ++j) {
    X[j] = read_int();
    Y[j] = read_int();
  }
  for (int i = 0; i < Q; ++i) {
    S[i] = read_int();
    E[i] = read_int();
    L[i] = read_int();
    R[i] = read_int();
  }

  std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
  for (size_t i = 0; i < A.size(); ++i) {
    printf("%d\n", A[i]);
  }
  return 0;
}
*/

Compilation message

werewolf.cpp: In function 'void filesin()':
werewolf.cpp:55:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void filesin(void){freopen("tracing.in","r",stdin);}
                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp: In function 'void filesout()':
werewolf.cpp:56:28: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void filesout(void){freopen("tracing.out","w",stdout);}
                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 694 ms 896 KB Output is correct
11 Correct 577 ms 888 KB Output is correct
12 Correct 445 ms 1016 KB Output is correct
13 Correct 713 ms 896 KB Output is correct
14 Correct 569 ms 888 KB Output is correct
15 Correct 1174 ms 1148 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 292 ms 46584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 694 ms 896 KB Output is correct
11 Correct 577 ms 888 KB Output is correct
12 Correct 445 ms 1016 KB Output is correct
13 Correct 713 ms 896 KB Output is correct
14 Correct 569 ms 888 KB Output is correct
15 Correct 1174 ms 1148 KB Output is correct
16 Runtime error 292 ms 46584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -