Submission #1020889

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1020889	2024-07-12T10:57:04 Z	JakobZorz	Werewolf (IOI18_werewolf)	C++17	Compilation error	0 ms	0 KB

werewolf

#include"werewolf.h"
#include<queue>
#include<iostream>
#include<set>
using namespace std;

int n,m,q;
vector<int>nodes[200000];

vector<bool>reachable2(int s,int t){
    vector<bool>vis(n);
    queue<int>q;
    q.push(s);
    while(q.size()){
        int node=q.front();
        q.pop();
        if(vis[node]||node<t)
            continue;
        vis[node]=true;
        for(int ne:nodes[node])
            q.push(ne);
    }
    return vis;
}

struct Query{
    int S,E,L,R;
    int ans;
};

bool cmp(Query*a,Query*b){
    return a->L<b->L;
}

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<n;i++){
        nodes[i].clear();
    }
    for(int i=0;i<m;i++){
        nodes[X[i]].push_back(Y[i]);
        nodes[Y[i]].push_back(X[i]);
    }
    
    vector<int>comp(n);
    vector<vector<int>>comps(n);
    
    for(int i=0;i<n;i++){
        comps[i]={i};
        set<int>to_add;
        for(int ne:nodes[i]){
            if(ne>i)
                continue;
            to_add.insert(comp[ne]);
        }
        for(int j:to_add){
            comps[i].insert(comps[i].end(),comps[j].begin(),comps[j].end());
            comps[i].push_back(i);
        }
        for(int j:comps[i])
            comp[j]=i;
    }
    vector<int>line=comps[comp[0]];
    /*for(int i:line)
        cout<<i<<" ";
    cout<<"\n";*/
    
    vector<int>res(q);
    vector<Query>qrs(q);
    
    for(int i=0;i<q;i++){
        qrs[i].S=S[i];
        qrs[i].E=E[i];
        qrs[i].L=L[i];
        qrs[i].R=R[i];
    }
    
    vector<Query*>srt;
    for(int i=0;i<n;i++)
        srt.push_back(&qrs[i]);
    
    sort(srt.begin(),srt.end(),cmp);
    
    for(auto qry:srt){
        vector<bool>v1=reachable2(qry->S,qry->L);
        vector<bool>v2(n);
        for(int j=0;j<(int)line.size();j++){
            if(line[j]==qry->E){
                for(int k=j;k<(int)line.size()&&line[k]<=qry->R;k++)
                    v2[line[k]]=true;
                for(int k=j;k>=0&&line[k]<=qry->R;k--)
                    v2[line[k]]=true;
                break;
            }
        }
        for(int j=0;j<n;j++)
            if(v1[j]&&v2[j])
                qry->ans=1;
    }
    
    for(int i=0;i<q;i++)
        res[i]=qrs[i].ans;
    
    return res;
}

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:84:5: error: 'sort' was not declared in this scope; did you mean 'srt'?
   84 |     sort(srt.begin(),srt.end(),cmp);
      |     ^~~~
      |     srt