답안 #417978

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
417978	2021-06-04T18:10:08 Z	LouayFarah	늑대인간 (IOI18_werewolf)	C++14	컴파일 오류	0 ms	0 KB

werewolf

#include "bits/stdc++.h"
#include "werewolf.h"
using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second

vector<vector<int>> adj;
vector<int> em;
vector<int> path;
vector<pair<int, int>> sorted_path;

void bfs(int n, int S, int E)
{
    vector<bool> visited(n, false);
    vector<int> parent(n, -1);
    queue<int> q;

    q.push(S);
    bool flag = true;
    visited[S] = true;

    while(!q.empty()&&flag)
    {
        int u = q.front();
        q.pop();

        visited[u] = true;

        for(auto v: adj[u])
        {
            if(visited[v])
                continue;
            parent[v] = u;
            q.push(v);
            if(v==E)
                flag = false;
        }
    }

    vector<int> p;
    int x = E;
    while(x!=-1)
    {
        p.pb(x);
        x = parent[x];
    }

    reverse(p.begin(), p.end());
    path = p;
}

int bs(int x)
{
    int l = 0, r = (int)sorted_path.size();
    while(l<=r)
    {
        int mid = l + (r-l)/2;
        if(sorted_path[mid].fi==x)
            return sorted_path[mid].se;
        if(sorted_path[mid].fi<x)
            l = mid+1;
        else
            r = mid-1;
    }
    return -1;
}

const int Q = 200000;
int* check_validity(int n, int x[], int y[], int s[], int e[], int l[], int r[])
{
    int m = n-1;
    int q = Q;
    int *res = new int[q];

    adj.assign(n, em);

    pair<int, int> boundary  = mp(-1, -1);
    for(int i  = 0; i<m; i++)
    {
        adj[x[i]].pb(y[i]);
        adj[y[i]].pb(x[i]);
    }

    for(int i = 0; i<n; i++)
    {
        if((int)adj[i].size()==1)
        {
            if(boundary.fi==-1)
                boundary.fi = i;
            else
            {
                boundary.se = i;
                break;
            }
        }
    }

    bfs(n, boundary.fi , boundary.se);
    int len = int(path.size());

    for(int i = 0; i<len; i++)
    {
        sorted_path.pb(mp(path[i], i));
    }
    sort(sorted_path.begin(), sorted_path.end());

    for(int querie = 0; querie<q; querie++)
    {
        int S = s[querie];
        int E = e[querie];
        int L = l[querie];
        int R = r[querie];

        bool flag = false;
        bool reversed = false;

        int ind_start = bs(S);
        int ind_end = bs(E);
        if(ind_end<ind_start)
            reversed = true;

        if(reversed)
        {
            int i = ind_start;
            int last = ind_start;
            while(i>ind_end)
            {
                if(path[i]>=L&&path[i]<=R)
                    last = i;
                if(path[i]<L)
                    break;
                i--;
            }

            if(i==ind_end)
                flag = true;
            else
            {
                i = last -1;
                while(i>ind_end)
                {
                    if(path[i]>R)
                        break;
                    i--;
                }
                if(i==ind_end)
                    flag = true;
            }
        }
        else
        {
            int i = ind_start;
            int last = ind_start;
            while(i<ind_end)
            {
                if(path[i]>=L&&path[i]<=R)
                    last = i;
                if(path[i]<L)
                    break;
                i++;
            }

            i = last + 1;
            while(i<ind_end)
            {
                if(path[i]>R)
                    break;
                i++;
            }
            if(i==ind_end)
                flag = true;
        }

        if(flag)
            res[querie] = 1;
        else
            res[querie] = 0;
    }
    return res;
}

Compilation message

/usr/bin/ld: /tmp/ccl7aO7b.o: in function `main':
grader.cpp:(.text.startup+0x377): undefined reference to `check_validity(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status