답안 #431638

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
431638 2021-06-17T13:56:40 Z Bench0310 늑대인간 (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 | }
      | ^
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4046 ms 26076 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 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 -