oj.uz

Submission #1024231

# Submission time Handle Problem Language Result Execution time Memory
1024231 2024-07-15T17:36:10 Z ksu2009en Werewolf (IOI18_werewolf) C++14
15 / 100
 4000 ms 32524 KB 
#include "werewolf.h"
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>

using namespace std;
typedef int ll;

pair<int, int> t[200007];
ll lead[200007];

ll findlead(ll v){
    if(lead[v] == v)
        return v;
    
    return lead[v] = findlead(lead[v]);
}

void unite(ll a, ll b){
    a = findlead(a), b = findlead(b);
    
    if(a == b)
        return;
    
    t[b].first = min(t[b].first, t[a].first);
    t[b].second = max(t[b].second, t[a].second);
    
    lead[a] = b;
}

vector<ll> d[200007];

bool used1[200007], used2[200007];

ll lim = 0;

void dfs1(ll v){
   if(v < lim)
       return;
   
   used1[v] = true;
   for(auto i: d[v]){
       if(!used1[i] && i >= lim)
           dfs1(i);
   }
}

void dfs2(ll v){
   if(v > lim)
       return;
   
   used2[v] = true;
   for(auto i: d[v]){
       if(!used2[i] && i <= lim)
           dfs2(i);
   }
}

vector<int> correct(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){
    
    for(int i = 0; i <= n; i++)
        d[i].clear(), used1[i] = used2[i] = false;
    
    ll q = l.size();
        
    for(int i = 0; i < x.size(); i++){
        d[x[i]].push_back(y[i]);
        d[y[i]].push_back(x[i]);
    }
    
    vector<int> ans;
    
    for(int i = 0; i < q; i++){
        lim = l[i];
        
        dfs1(s[i]);
        lim = r[i];
        dfs2(e[i]);
        
        int res = 0;
        for(int j = 0; j < n; j++){
            if(used1[j] && used2[j]){
                res = 1;
            }
            
            used1[j] = used2[j] = 0;
        }
        
        ans.push_back(res);
    }
    return ans;
}

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) {
    
    return correct(n, x, y, s, e, l, r);
    
    for(int i = 0; i <= n; i++)
        d[i].clear();
    
    ll q = l.size();
    for(int i = 0; i < q; i++)
        s[i]++, e[i]++, l[i]++, r[i]++;
    
    for(int i = 0; i < x.size(); i++){
        x[i]++, y[i]++;
        
        d[min(x[i], y[i])].push_back(max(x[i], y[i]));
    }
    
    vector<int> ans(q);
    
    vector<vector<int>> g(n + 1);
    for(int i = 0; i < q; i++)
        g[l[i]].push_back(i);
    
    for(int i = 1; i <= n; i++){
        lead[i] = i;
        t[i].first = t[i].second = i;
    }
    
    for(int i = n; i >= 1; i--){
        for(auto j: d[i])
            unite(i, j);
        
        for(auto j: g[i]){
            if(t[findlead(s[j])].first <= r[j]){
                ans[j]++;
            }
        }
    }
    
    for(int i = 1; i <= n; i++){
        lead[i] = i;
        t[i].first = t[i].second = i;
    }
    
    for(int i = 1; i <= n; i++)
        g[i].clear();
    
    for(int i = 0; i < q; i++){
        g[r[i]].push_back(i);
    }
    
    for(int i = 1; i <= n; i++)
        d[i].clear();
    
    for(int i = 0; i < x.size(); i++){
        d[max(x[i], y[i])].push_back(min(x[i], y[i]));
    }
    
    for(int i = 1; i <= n; i++){
        for(auto j: d[i])
            unite(i, j);
        
        for(auto j: g[i]){
            if(t[findlead(e[j])].second >= l[j])
                ans[j]++;
        }
    }
    
    for(int i = 0; i < q; i++)
        ans[i] = (ans[i] == 2 ? 1 : 0);
    
    return ans;
}
/*
 6 6 1
 0 3
 3 1
 3 4
 1 2
 2 5
 1 5
 5 3 2 5
 
 */

/*
 6 6 1
 0 3
 3 1
 3 4
 1 2
 2 5
 1 5
 5 4 3 4
 
 
 4 2 1 2
 
 4 2 2 2
 5 4 3 4
 */

/*
 4 3 1
 3 0
 0 1
 1 2
 3 2 2 2
 
 */
/*
 4 3 1
 3 1
 1 0
 2 0
 3 2 1 2
 
 */

Compilation message

werewolf.cpp: In function 'std::vector<int> correct(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:82:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for(int i = 0; i < x.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:123:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     for(int i = 0; i < x.size(); i++){
      |                    ~~^~~~~~~~~~
werewolf.cpp:166:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |     for(int i = 0; i < x.size(); i++){
      |                    ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 157 ms 6748 KB Output is correct
11 Correct 61 ms 6744 KB Output is correct
12 Correct 23 ms 7004 KB Output is correct
13 Correct 180 ms 6924 KB Output is correct
14 Correct 76 ms 6748 KB Output is correct
15 Correct 169 ms 7004 KB Output is correct

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 157 ms 6748 KB Output is correct
11 Correct 61 ms 6744 KB Output is correct
12 Correct 23 ms 7004 KB Output is correct
13 Correct 180 ms 6924 KB Output is correct
14 Correct 76 ms 6748 KB Output is correct
15 Correct 169 ms 7004 KB Output is correct
16 Execution timed out 4021 ms 32524 KB Time limit exceeded
17 Halted 0 ms 0 KB -