oj.uz

Submission #600893

# Submission time Handle Problem Language Result Execution time Memory
600893 2022-07-21T08:49:34 Z enerelt14 Werewolf (IOI18_werewolf) C++14
15 / 100
 319 ms 32460 KB 
#include "werewolf.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
struct node{
    int mn, mx;
    node(){
        mn=mx=0;
    }
};
bool vis[3005], is[3005];
vector<int>adj[3005];
void dijkstra1(int s, int l){
    queue<int>pq;
    pq.push(s);
    while(!pq.empty()){
        int u=pq.front();
        pq.pop();
        vis[u]=1;
        for (int i=0;i<adj[u].size();i++){
            if (adj[u][i]<l || vis[adj[u][i]])continue;
            pq.push(adj[u][i]);
        }
        while(!pq.empty() && vis[pq.front()])pq.pop();
    }
}
void dijkstra2(int s, int r){
    queue<int>pq;
    pq.push(s);
    while(!pq.empty()){
        int u=pq.front();
        pq.pop();
        vis[u]=1;
        for (int i=0;i<adj[u].size();i++){
            if (adj[u][i]>r || vis[adj[u][i]])continue;
            pq.push(adj[u][i]);
        }
        while(!pq.empty() && vis[pq.front()])pq.pop();
    }
}
int x[200005], num[200005], pos[200005];
node tree[800005];
void build(int id, int l, int r){
    if (l==r){
        tree[id].mn=x[l];
        tree[id].mx=x[l];
        return;
    }
    int mid=(l+r)/2;
    build(id*2+1, l, mid);
    build(id*2+2, mid+1, r);
    tree[id].mn=min(tree[id*2+1].mn, tree[id*2+2].mn);
    tree[id].mx=max(tree[id*2+1].mx, tree[id*2+2].mx);
}
int querymn(int id, int l, int r, int L, int R){
    if (L>r || l>R)return INT_MAX;
    if (L<=l && r<=R)return tree[id].mn;
    int mid=(l+r)/2;
    return min(querymn(id*2+1, l, mid, L, R), querymn(id*2+2, mid+1, r, L, R));
}
int querymx(int id, int l, int r, int L, int R){
    if (L>r || l>R)return 0;
    if (L<=l && r<=R)return tree[id].mx;
    int mid=(l+r)/2;
    return max(querymx(id*2+1, l, mid, L, R), querymx(id*2+2, mid+1, r, L, R));
}
vector<int>check_validity(int N,vector<int>X,vector<int>Y,vector<int>S,vector<int>E,vector<int>L,vector<int>R){
    if (N<=3000 && X.size()<=6000 && S.size()<=3000){
        for (int i=0;i<X.size();i++){
            adj[X[i]].pb(Y[i]);
            adj[Y[i]].pb(X[i]);
        }
        int Q=S.size();
        vector<int>ans;
        for (int j=0;j<Q;j++){
            ans.pb(0);
            if (S[j]<L[j] || E[j]>R[j])continue;
            for (int i=L[j];i<N;i++)vis[i]=0;
            dijkstra1(S[j], L[j]);
            for (int i=L[j];i<=R[j];i++)is[i]=vis[i];
            for (int i=0;i<=R[j];i++)vis[i]=0;
            dijkstra2(E[j], R[j]);
            for (int i=L[j];i<=R[j];i++){
                if (vis[i] && is[i]){
                    ans[j]=1;
                    break;
                }
            }
        }
        return ans;
    }
    for (int i=0;i<X.size();i++){
        adj[X[i]].pb(Y[i]);
        adj[Y[i]].pb(X[i]);
    }
    x[0]=N;
    for (int i=0;i<N;i++){
        if (adj[i].size()==1){
            x[1]=i;
            break;
        }
    }
    for (int i=2;i<=N;i++){
        if (adj[x[i-1]][0]==x[i-2])x[i]=adj[x[i-1]][1];
        else x[i]=adj[x[i-1]][0];
    }
    for (int i=1;i<=N;i++)pos[x[i]]=i;
    build(0, 1, N);
    vector<int>ans;
    for (int i=0;i<S.size();i++){
        ans.pb(0);
        if (S[i]<L[i] && E[i]>R[i])continue;
        if (pos[S[i]]==pos[E[i]]){
            ans[i]=1;
            continue;
        }
        if (pos[S[i]]>pos[E[i]]){
            int l=1, r=pos[S[i]];
            while(l!=r){
                int mid=(l+r)/2;
                if (querymn(0, 1, N, mid, r)>=L[i])r=mid;
                else l=mid+1;
            }
            if (l<=pos[E[i]] || querymx(0, 1, N, pos[E[i]], l)<=R[i])ans[i]=1;
        }else{
            int l=pos[S[i]], r=N;
            while(l!=r){
                int mid=(l+r)/2;
                if (querymn(0, 1, N, l, mid+1)>=L[i])l=mid+1;
                else r=mid;
            }
            if (l>=pos[E[i]] || querymx(0, 1, N, l, pos[E[i]])<=R[i])ans[i]=1;
        }
    }
    return ans;
}

Compilation message

werewolf.cpp: In function 'void dijkstra1(int, int)':
werewolf.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         for (int i=0;i<adj[u].size();i++){
      |                      ~^~~~~~~~~~~~~~
werewolf.cpp: In function 'void dijkstra2(int, int)':
werewolf.cpp:34:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for (int i=0;i<adj[u].size();i++){
      |                      ~^~~~~~~~~~~~~~
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:69:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for (int i=0;i<X.size();i++){
      |                      ~^~~~~~~~~
werewolf.cpp:92:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for (int i=0;i<X.size();i++){
      |                  ~^~~~~~~~~
werewolf.cpp:110:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for (int i=0;i<S.size();i++){
      |                  ~^~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6612 KB Output is correct
2 Correct 4 ms 6612 KB Output is correct
3 Correct 4 ms 6664 KB Output is correct
4 Correct 3 ms 6612 KB Output is correct
5 Correct 3 ms 6612 KB Output is correct
6 Correct 4 ms 6612 KB Output is correct
7 Correct 4 ms 6612 KB Output is correct
8 Correct 4 ms 6612 KB Output is correct
9 Correct 5 ms 6612 KB Output is correct
10 Correct 239 ms 6908 KB Output is correct
11 Correct 136 ms 6884 KB Output is correct
12 Correct 22 ms 6868 KB Output is correct
13 Correct 270 ms 6892 KB Output is correct
14 Correct 173 ms 6872 KB Output is correct
15 Correct 319 ms 7092 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 124 ms 32460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6612 KB Output is correct
2 Correct 4 ms 6612 KB Output is correct
3 Correct 4 ms 6664 KB Output is correct
4 Correct 3 ms 6612 KB Output is correct
5 Correct 3 ms 6612 KB Output is correct
6 Correct 4 ms 6612 KB Output is correct
7 Correct 4 ms 6612 KB Output is correct
8 Correct 4 ms 6612 KB Output is correct
9 Correct 5 ms 6612 KB Output is correct
10 Correct 239 ms 6908 KB Output is correct
11 Correct 136 ms 6884 KB Output is correct
12 Correct 22 ms 6868 KB Output is correct
13 Correct 270 ms 6892 KB Output is correct
14 Correct 173 ms 6872 KB Output is correct
15 Correct 319 ms 7092 KB Output is correct
16 Runtime error 124 ms 32460 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -