제출 #233729

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
233729		Theo830	늑대인간 (IOI18_werewolf)	C++17	15 / 100	1174 ms	46584 KiB

werewolf

#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;
}
*/

컴파일 시 표준 에러 (stderr) 메시지

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 / 7
• Subtask 2: 8 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51