Submission #1073832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073832		oscar1f	Werewolf (IOI18_werewolf)	C++17	100 / 100	3103 ms	106684 KiB

werewolf

#include<bits/stdc++.h>
#include "werewolf.h"

using namespace std;

const int MAX_SOM=200*1000+5,MAX_REQ=200*1000+5;
int nbSom,nbAre,nbReq,numEuler;
int pere[MAX_SOM];
vector<int> adjaGrand[MAX_SOM],adjaPetit[MAX_SOM];
vector<pair<int,int>> reqHom[MAX_SOM],reqLoup[MAX_SOM];
int numHom[MAX_REQ],numLoup[MAX_REQ];
vector<int> rep;
int pereHom[MAX_SOM],pereLoup[MAX_SOM];
vector<int> filsHom[MAX_SOM],filsLoup[MAX_SOM];
int eulerHomme[MAX_SOM][2],eulerLoup[MAX_SOM][2];
int idSom[MAX_SOM];
vector<tuple<int,int,int>> quest[MAX_SOM];
vector<int> enCours;
int dessus[MAX_SOM],somTot[MAX_SOM];
int diff[MAX_SOM];

int find(int pos) {
    if (pos!=pere[pos]) {
        pere[pos]=find(pere[pos]);
    }
    return pere[pos];
}

void DFS_homme(int pos) {
    numEuler++;
    idSom[numEuler]=pos;
    eulerHomme[pos][0]=numEuler;
    for (int i:filsHom[pos]) {
        DFS_homme(i);
    }
    eulerHomme[pos][1]=numEuler;
}

void DFS_loup(int pos) {
    numEuler++;
    eulerLoup[pos][0]=numEuler;
    for (int i:filsLoup[pos]) {
        DFS_loup(i);
    }
    eulerLoup[pos][1]=numEuler;
}

bool inclusLoup(int petit,int grand) {
    return (eulerLoup[grand][0]<=eulerLoup[petit][0] and eulerLoup[grand][1]>=eulerLoup[petit][1]);
}

void remonte(int pos) {
    somTot[pos]=dessus[pos];
    for (int i:filsLoup[pos]) {
        remonte(i);
        somTot[pos]+=somTot[i];
    }
}

int calc(int pos) {
    int ans=somTot[pos];
    for (int i:enCours) {
        if (inclusLoup(i,pos)) {
            ans++;
        }
    }
    return ans;
}

vector<int> check_validity(int N,vector<int> X,vector<int> Y,vector<int> S,vector<int> E,vector<int> L,vector<int> R) {
    nbSom=N;
    nbAre=X.size();
    nbReq=S.size();
    int debAre,finAre;
    for (int i=0;i<nbAre;i++) {
        debAre=min(X[i],Y[i]);
        finAre=max(X[i],Y[i]);
        adjaGrand[debAre].push_back(finAre);
        adjaPetit[finAre].push_back(debAre);
    }
    for (int i=0;i<nbReq;i++) {
        reqHom[L[i]].push_back({S[i],i});
        reqLoup[R[i]].push_back({E[i],i});
    }
    for (int i=0;i<nbSom;i++) {
        pere[i]=i;
    }
    for (int i=nbSom-1;i>=0;i--) {
        for (int j:adjaGrand[i]) {
            if (find(j)!=i) {
                pereHom[find(j)]=i;
                filsHom[i].push_back(find(j));
                pere[find(j)]=i;
            }
        }
        for (auto j:reqHom[i]) {
            numHom[j.second]=find(j.first);
        }
    }
    for (int i=0;i<nbSom;i++) {
        pere[i]=i;
    }
    for (int i=0;i<nbSom;i++) {
        for (int j:adjaPetit[i]) {
            if (find(j)!=i) {
                pereLoup[find(j)]=i;
                filsLoup[i].push_back(find(j));
                pere[find(j)]=i;
            }
        }
        for (auto j:reqLoup[i]) {
            numLoup[j.second]=find(j.first);
        }
    }
    /*for (int i=0;i<nbReq;i++) {
        cout<<numHom[i]<<" "<<numLoup[i]<<endl;
    }*/
    numEuler=-1;
    DFS_homme(0);
    DFS_loup(nbSom-1);
    /*for (int i=0;i<nbSom;i++) {
        cout<<i<<" : ";
        for (int j:filsHom[i]) {
            cout<<j<<" ";
        }
        cout<<endl;
    }
    for (int i=0;i<nbSom;i++) {
        cout<<i<<" : ";
        for (int j:filsLoup[i]) {
            cout<<j<<" ";
        }
        cout<<endl;
    }
    for (int i=0;i<nbSom;i++) {
        cout<<i<<" : "<<eulerLoup[i][0]<<" "<<eulerLoup[i][1]<<endl;
    }*/
    for (int i=0;i<nbReq;i++) {
        if (eulerHomme[numHom[i]][0]>0) {
            quest[eulerHomme[numHom[i]][0]-1].push_back(make_tuple(numLoup[i],i,-1)); ////à voir
        }
        quest[eulerHomme[numHom[i]][1]].push_back(make_tuple(numLoup[i],i,1)); ////à voir
    }
    for (int i=0;i<nbSom;i++) {
        if(i%(int)sqrt(nbSom)==0) {
            for (int j:enCours) {
                dessus[j]++;
            }
            enCours.clear();
            remonte(nbSom-1);
        }
        enCours.push_back(idSom[i]);
        for (auto j:quest[i]) {
            diff[get<1>(j)]+=calc(get<0>(j))*get<2>(j);
        }
    }
    for (int i=0;i<nbReq;i++) {
        if (diff[i]<=0) {
            rep.push_back(0);
        }
        else {
            rep.push_back(1);
        }
    }
    return rep;
}

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51