oj.uz

Submission #431638

# Submission time Handle Problem Language Result Execution time Memory
431638 2021-06-17T13:56:40 Z Bench0310 Werewolf (IOI18_werewolf) C++17
15 / 100
 4000 ms 26076 KB 
#include <bits/stdc++.h>
#include "werewolf.h"

using namespace std;
typedef long long ll;

const int N=200005;
int n,m,q;
vector<int> v[N];

vector<int> solve_small(vector<int> ns,vector<int> ne,vector<int> nl,vector<int> nr)
{
    vector<int> res(q,0);
    for(int o=0;o<q;o++)
    {
        int s=ns[o];
        int e=ne[o];
        int l=nl[o];
        int r=nr[o];
        vector<array<int,2>> dp(n,{0,0});
        queue<array<int,2>> b;
        auto add=[&](int a,int t)
        {
            if(dp[a][t]==0)
            {
                dp[a][t]=1;
                b.push({a,t});
            }
        };
        add(s,0);
        while(!b.empty())
        {
            auto [a,t]=b.front();
            b.pop();
            if(l<=a&&a<=r&&t==0) add(a,1);
            for(int to:v[a])
            {
                if(t==0&&to>=l) add(to,0);
                if(t==1&&to<=r) add(to,1);
            }
        }
        res[o]=dp[e][1];
    }
    return res;
}

vector<int> check_validity(int nn,vector<int> nx,vector<int> ny,vector<int> ns,vector<int> ne,vector<int> nl,vector<int> nr)
{
    n=nn;
    m=nx.size();
    q=ns.size();
    for(int i=0;i<m;i++)
    {
        v[nx[i]].push_back(ny[i]);
        v[ny[i]].push_back(nx[i]);
    }
    if(n<=3000&&m<=6000&&q<=3000) return solve_small(ns,ne,nl,nr);
}

//int main()
//{
//    
//    return 0;
//}

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:58:1: warning: control reaches end of non-void function [-Wreturn-type]
   58 | }
      | ^

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 5 ms 4940 KB Output is correct
3 Correct 4 ms 4996 KB Output is correct
4 Correct 5 ms 4940 KB Output is correct
5 Correct 5 ms 5004 KB Output is correct
6 Correct 5 ms 4940 KB Output is correct
7 Correct 6 ms 4996 KB Output is correct
8 Correct 5 ms 4940 KB Output is correct
9 Correct 5 ms 4940 KB Output is correct
10 Correct 452 ms 5420 KB Output is correct
11 Correct 306 ms 5400 KB Output is correct
12 Correct 34 ms 5400 KB Output is correct
13 Correct 386 ms 5416 KB Output is correct
14 Correct 254 ms 5396 KB Output is correct
15 Correct 303 ms 5528 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4046 ms 26076 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 5 ms 4940 KB Output is correct
3 Correct 4 ms 4996 KB Output is correct
4 Correct 5 ms 4940 KB Output is correct
5 Correct 5 ms 5004 KB Output is correct
6 Correct 5 ms 4940 KB Output is correct
7 Correct 6 ms 4996 KB Output is correct
8 Correct 5 ms 4940 KB Output is correct
9 Correct 5 ms 4940 KB Output is correct
10 Correct 452 ms 5420 KB Output is correct
11 Correct 306 ms 5400 KB Output is correct
12 Correct 34 ms 5400 KB Output is correct
13 Correct 386 ms 5416 KB Output is correct
14 Correct 254 ms 5396 KB Output is correct
15 Correct 303 ms 5528 KB Output is correct
16 Execution timed out 4046 ms 26076 KB Time limit exceeded
17 Halted 0 ms 0 KB -