oj.uz

답안 #1024231

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1024231 2024-07-15T17:36:10 Z ksu2009en 늑대인간 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4021 ms 32524 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 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 -