oj.uz

Submission #90623

# Submission time Handle Problem Language Result Execution time Memory
90623 2018-12-23T01:54:14 Z Retro3014 Werewolf (IOI18_werewolf) C++17
15 / 100
 314 ms 34248 KB 
#include "werewolf.h"
#include <vector>
#include <algorithm>

using namespace std;
#define MAX_N 200000

int n, m, q;
vector<int> graph[MAX_N+1], s, e, l, r;

vector<int> solve1();

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    n=N; m=(int)X.size(); q=(int)S.size();
    for(int i=0; i<m; i++){
        graph[X[i]].push_back(Y[i]);
        graph[Y[i]].push_back(X[i]);
    }
    for(int i=0; i<q; i++){
        s.push_back(S[i]);
        e.push_back(E[i]);
        l.push_back(L[i]);
        r.push_back(R[i]);
    }
    if(n<=3000 && m<=6000 && q<=3000){
        return solve1();
    }
    return s;
}

int visited[MAX_N+1];

void dfs1(int x, int y){
    if(visited[x]>0){
        return;
    }
    if(x<y){
        return;
    }
    visited[x]++;
    for(int i=0; i<graph[x].size(); i++){
        dfs1(graph[x][i], y);
    }
}

void dfs2(int x, int y){
    if(visited[x]>=2){
        return;
    }
    if(x>y){
        return;
    }
    visited[x]+=2;
    for(int i=0; i<graph[x].size(); i++){
        dfs2(graph[x][i], y);
    }
}

vector<int> solve1(){
    vector<int> ans(q);
    for(int t=0; t<q; t++){
        dfs1(s[t], l[t]);
        dfs2(e[t], r[t]);
        for(int i=0; i<n; i++){
            if(visited[i]==3){
                ans[t]=1;
            }
            visited[i]=0;
        }
    }
    return ans;
}

Compilation message

werewolf.cpp: In function 'void dfs1(int, int)':
werewolf.cpp:41:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<graph[x].size(); i++){
                  ~^~~~~~~~~~~~~~~~
werewolf.cpp: In function 'void dfs2(int, int)':
werewolf.cpp:54:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<graph[x].size(); i++){
                  ~^~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 5 ms 5116 KB Output is correct
3 Correct 6 ms 5228 KB Output is correct
4 Correct 5 ms 5228 KB Output is correct
5 Correct 5 ms 5228 KB Output is correct
6 Correct 6 ms 5356 KB Output is correct
7 Correct 6 ms 5356 KB Output is correct
8 Correct 6 ms 5356 KB Output is correct
9 Correct 6 ms 5356 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 5 ms 5116 KB Output is correct
3 Correct 6 ms 5228 KB Output is correct
4 Correct 5 ms 5228 KB Output is correct
5 Correct 5 ms 5228 KB Output is correct
6 Correct 6 ms 5356 KB Output is correct
7 Correct 6 ms 5356 KB Output is correct
8 Correct 6 ms 5356 KB Output is correct
9 Correct 6 ms 5356 KB Output is correct
10 Correct 274 ms 5856 KB Output is correct
11 Correct 171 ms 6020 KB Output is correct
12 Correct 26 ms 6240 KB Output is correct
13 Correct 314 ms 6244 KB Output is correct
14 Correct 200 ms 6368 KB Output is correct
15 Correct 252 ms 6600 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 246 ms 34248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 5 ms 5116 KB Output is correct
3 Correct 6 ms 5228 KB Output is correct
4 Correct 5 ms 5228 KB Output is correct
5 Correct 5 ms 5228 KB Output is correct
6 Correct 6 ms 5356 KB Output is correct
7 Correct 6 ms 5356 KB Output is correct
8 Correct 6 ms 5356 KB Output is correct
9 Correct 6 ms 5356 KB Output is correct
10 Correct 274 ms 5856 KB Output is correct
11 Correct 171 ms 6020 KB Output is correct
12 Correct 26 ms 6240 KB Output is correct
13 Correct 314 ms 6244 KB Output is correct
14 Correct 200 ms 6368 KB Output is correct
15 Correct 252 ms 6600 KB Output is correct
16 Incorrect 246 ms 34248 KB Output isn't correct
17 Halted 0 ms 0 KB -