oj.uz

답안 #1073675

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1073675 2024-08-24T17:48:41 Z oscar1f 늑대인간 (IOI18_werewolf) C++17
0 / 100
 4000 ms 53328 KB 
#include<bits/stdc++.h>
#include "werewolf.h"

using namespace std;

const int MAX_SOM=200*1000+5;
int nbSom,nbAre,nbBlocs,nbReq;
vector<int> rep;
int bloc[MAX_SOM];
vector<int> listeBloc[MAX_SOM];
vector<pair<int,int>> ajout[MAX_SOM][2];
int pere[2*MAX_SOM],prof[2*MAX_SOM];
vector<pair<int,int>> modifProf,modifPere;
vector<tuple<int,int,int,int,int>> reqBloc[MAX_SOM];

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

void unir(int deb,int fin,int supp) {
    deb=find(deb);
    fin=find(fin);
    if (deb!=fin) {
        if (prof[deb]>prof[fin]) {
            swap(deb,fin);
        }
        if (supp==1) {
            modifPere.push_back({deb,pere[deb]});
            modifProf.push_back({fin,prof[fin]});
        }
        prof[fin]=max(prof[fin],prof[deb]+1);
        pere[deb]=fin;
    }
}

void init() {
    for (int i=0;i<2*nbSom;i++) {
        pere[i]=i;
        prof[i]=1;
    }
    for (int i=0;i<nbSom;i++) {
        unir(i,i+nbSom,0);
    }
}

void ajoutAre(int pos,int tab,int supp) {
    for (auto i:ajout[pos][tab]) {
        unir(i.first,i.second,supp);
    }
}

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();
    rep.resize(nbReq);
    int debAre,finAre;
    for (int i=0;i<nbSom;i++) {
        debAre=min(X[i],Y[i]);
        finAre=max(X[i],Y[i]);
        ajout[debAre][0].push_back({debAre,finAre});
        ajout[finAre][1].push_back({finAre+nbSom,debAre+nbSom});
    }
    int tailleEnCours,pos=0; 
    while (pos<nbSom) {
        nbBlocs++;
        tailleEnCours=0;
        while (pos<nbSom and tailleEnCours<=sqrt(nbAre)) {
            bloc[pos]=nbBlocs;
            listeBloc[nbBlocs].push_back(pos);
            pos++;
            tailleEnCours+=ajout[pos][0].size()+2*nbAre;
        }
    }
    /*for (int i=1;i<=nbBlocs;i++) {
        for (int j:listeBloc[i]) {
            cout<<j<<" ";
        }
        cout<<endl;
    }*/
    for (int i=0;i<nbReq;i++) {
        reqBloc[bloc[L[i]]].push_back({R[i],L[i],S[i],E[i],i});
    }
    int maxLoup,minHom,somDeb,somFin,dernLoup,idReq;
    for (int iBloc=nbBlocs;iBloc>0;iBloc--) {
        init();
        sort(reqBloc[iBloc].begin(),reqBloc[iBloc].end());
        for (int i=listeBloc[iBloc].back();i<nbSom;i++) {
            ajoutAre(i,0,0);
        }
        dernLoup=-1;
        for (auto j:reqBloc[iBloc]) {
            maxLoup=get<0>(j);
            minHom=get<1>(j);
            somDeb=get<2>(j);
            somFin=get<3>(j);
            idReq=get<4>(j);
            for (int i=dernLoup+1;i<=maxLoup;i++) {
                ajoutAre(i,1,0);
            }
            modifPere.clear();
            modifProf.clear();
            for (int i=listeBloc[iBloc].back()-1;i>=minHom;i--) {
                ajoutAre(i,0,1);
            }
            if (find(somDeb)==find(somFin+nbSom)) {
                rep[idReq]=1;
            }
            while (!modifPere.empty()) {
                pere[modifPere.back().first]=modifPere.back().second;
                modifPere.pop_back();
            }
            while (!modifProf.empty()) {
                prof[modifProf.back().first]=modifProf.back().second;
                modifProf.pop_back();
            }
        }
    }
    return rep;
}

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 22364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 22364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

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

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 22364 KB Output isn't correct
2 Halted 0 ms 0 KB -