oj.uz

답안 #382989

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
382989 2021-03-28T16:37:40 Z mohamedsobhi777 늑대인간 (IOI18_werewolf) C++14
15 / 100
 871 ms 24448 KB 
#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int N = 3000 + 7;

int n, m;
vector<int> le, ri;

struct dsu
{
       int fat[N];
       dsu()
       {
              iota(fat, fat + N, 0);
       }
       int find(int x) { return fat[x] = x == fat[x] ? x : find(fat[x]); }
       void link(int u, int v)
       {
              u = find(u), v = find(v);
              fat[u] = v;
       }
       inline bool same(int u, int v) { return find(u) == find(v); }
};

bool solve(int st, int en, int L, int R)
{
       dsu d1, d2;
       for (int i = 0; i < m; ++i)
       {
              int u = le[i], v = ri[i];
              if (max(u, v) <= R)
                     d1.link(u, v);
              if (min(u, v) >= L)
                     d2.link(u, v);
       }
       for (int i = L; i <= R; ++i)
       {
              if (d1.same(en, i) && d2.same(st, i))
                     return 1;
       }

       return 0;
}

std::vector<int> check_validity(int _N, std::vector<int> X, std::vector<int> Y,
                                std::vector<int> S, std::vector<int> E,
                                std::vector<int> L, std::vector<int> R)
{
       n = _N, m = X.size();
       le = X, ri = Y;
       int Q = S.size();
       std::vector<int> A(Q);

       for (int i = 0; i < Q; ++i)
       {
              A[i] = solve(S[i], E[i], L[i], R[i]);
       }

       return A;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 394 ms 492 KB Output is correct
11 Correct 313 ms 672 KB Output is correct
12 Correct 256 ms 620 KB Output is correct
13 Correct 394 ms 748 KB Output is correct
14 Correct 298 ms 640 KB Output is correct
15 Correct 871 ms 876 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 179 ms 24448 KB Execution killed with signal 7
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 394 ms 492 KB Output is correct
11 Correct 313 ms 672 KB Output is correct
12 Correct 256 ms 620 KB Output is correct
13 Correct 394 ms 748 KB Output is correct
14 Correct 298 ms 640 KB Output is correct
15 Correct 871 ms 876 KB Output is correct
16 Runtime error 179 ms 24448 KB Execution killed with signal 7
17 Halted 0 ms 0 KB -