답안 #969507

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
969507 2024-04-25T08:53:26 Z tnknguyen_ 늑대인간 (IOI18_werewolf) C++17
컴파일 오류
0 ms 0 KB
#include <bits/stdc++.h>
using namespace std;
#define endl '\n' 
#define vi vector<int>
#define pii pair<int, int>

const int MX = 2e5 + 5;
vector<int> gr[4][MX];
int vis[MX];
int n, m, q;
vi X, Y, S, E, L, R;

struct KRT{
    int n;
    vector<int> p;

    KRT(int N){
        this->n = N;
        p.assign(N + 5, 0);
        for(int i=1; i<=n; ++i){
            p[i] = i;
        }    
    }

    int get(int u){
        return (u == p[u] ? u : p[u] = get(p[u]));
    }

    void add(int u, int v, int k){
        u = get(u), v = get(v);
        if(u == v){
            return;
        }
        p[v] = u;
        gr[k][u].push_back(v);
    }
};

struct BIT{
    int n;
    vector<int> f;

    BIT(int N){
        this->n = N + 5;
        f.assign(N + 5, 0);
    }

    void update(int i, int val){
        while(i < n){
            f[i] += val;
            i += (i & -i);
        }
    }

    int get(int i){
        int ans = 0;
        while(i > 0){
            ans += f[i];
            i -= (i & -i);
        }
        return ans;
    }
    int get(int l, int r){
        return get(r) - get(l - 1);
    }
};

struct query{
    int l, r, e, s, idx;
};

int in[4][MX], ou[4][MX];
int eu[4][MX];
int id = 0;
void dfs(int u, int p, int k){
    eu[k][++id] = u;
    in[k][u] = id;
    for(int v : gr[k][u]){
        if(v != p){
            dfs(v, u, k);
            eu[k][++id] = u;
            ou[k][u] = id;
        }
    }
}

vi check_validity(int n, vi X, vi Y, vi S, vi E, vi L, vi R){ //returns boolean vector.
    for(int i=0; i<m; ++i){
        int u = X[i], v = Y[i];
        gr[1][u].push_back(v);
        gr[1][v].push_back(u);
    }
    KRT up(n), dn(n);
    for(int i=1; i<=n; ++i){
        for(int u : gr[1][i]){
            if(vis[u] == 1){
                up.add(i, u, 2);
            }
        }
        vis[i] = 1;
    }   
    for(int i=n; i>=1; --i){
        for(int u : gr[1][i]){
            if(vis[u] == 2){
                dn.add(i, u, 3);
            }
        }
        vis[i] = 2;
    }

    for(int i=1; i<=n; ++i){
        if(up.get(i) == i){
            dfs(i, 0, 2);
            break;
        }
    }
    id = 0;
    for(int i=1; i<=n; ++i){
        if(dn.get(i) == i){
            dfs(i, 0, 3);
            break;
        }
    }

    vector<query> Q;
    vector<int> ans;
    for(int i=0; i<q; ++i){
        int s = S[i], e = E[i], l = L[i], r = R[i];
        // Q.push_back({l, r, s, e, i});
        set<int> se;
        for(int j=in[3][l]+1; j<ou[3][l]; ++j){
            // cout<<eu[3][j]<<' ';
            se.insert(eu[3][j]);
        }
        // cout<<" -- ";
        int f = 0;
        for(int j=in[2][r]+1; j<ou[2][r]; ++j){
            if(se.find(eu[2][j]) != se.end()){
                f = 1;
                // break;
            }
            // cout<<eu[2][j]<<' ';
        }
        // cout<<endl;
        ans.push_back(f);
    }
    // sort(Q.begin(), Q.end(), [](query u, query v){
    //     return (u.l < v.l);
    // });
    return ans;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

//    freopen("main.inp","r",stdin);
//    freopen("main.out","w",stdout);

    cin>>n>>m>>q;
    for(int i=1; i<=m; ++i){
        int u, v;
        cin>>u>>v;
        ++u, ++v;
        X.push_back(u);
        Y.push_back(v);
    }
    for(int i=1; i<=q; ++i){
        int s, e, l, r;
        cin>>s>>e>>l>>r;
        ++s, ++e, ++l, ++r;
        S.push_back(s), E.push_back(e), L.push_back(l), R.push_back(r);
    }

    vector<int> ans = check_validity(n, X, Y, S, E, L, R);
    for(int x : ans){
        cout<<x<<' ';
    }

    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:128:13: warning: unused variable 's' [-Wunused-variable]
  128 |         int s = S[i], e = E[i], l = L[i], r = R[i];
      |             ^
werewolf.cpp:128:23: warning: unused variable 'e' [-Wunused-variable]
  128 |         int s = S[i], e = E[i], l = L[i], r = R[i];
      |                       ^
/usr/bin/ld: /tmp/ccOq5PKO.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccuJYwEM.o:werewolf.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status