oj.uz

Submission #233713

# Submission time Handle Problem Language Result Execution time Memory
233713 2020-05-21T13:29:59 Z Theo830 Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 34168 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;}seg[4000000];
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
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;
}
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);
    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]);
        //arrout(visit,n);
        //cout<<endl;
        //arrout(visit2,n);
        //cout<<endl<<endl;
        ans[i] = 0;
        f(j,l[i],r[i]+1){
            ans[i] = max(ans[i],(ll)(visit[j] == 1 && visit2[j] == 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 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 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 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 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 699 ms 1004 KB Output is correct
11 Correct 580 ms 992 KB Output is correct
12 Correct 434 ms 1144 KB Output is correct
13 Correct 702 ms 1016 KB Output is correct
14 Correct 566 ms 1016 KB Output is correct
15 Correct 1187 ms 1152 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4101 ms 34168 KB Time limit exceeded
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 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 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 699 ms 1004 KB Output is correct
11 Correct 580 ms 992 KB Output is correct
12 Correct 434 ms 1144 KB Output is correct
13 Correct 702 ms 1016 KB Output is correct
14 Correct 566 ms 1016 KB Output is correct
15 Correct 1187 ms 1152 KB Output is correct
16 Execution timed out 4101 ms 34168 KB Time limit exceeded
17 Halted 0 ms 0 KB -