| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1016782 | 2024-07-08T12:19:45 Z | Noname_1900 | 늑대인간 (IOI18_werewolf) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 200000;
vector<int> chemins[NMAX];
int dejaVu[NMAX][2];
int liste[NMAX];
int position[NMAX];
int petitGrand[2][NMAX][20];
#define INFINI 1000000000
void lister(int noeud, int iListe, int anc)
{
liste[iListe] = noeud;
position[noeud] = iListe;
for(int pro : chemins[noeud])
{
if(pro == anc) continue;
lister(pro, iListe+1, noeud);
}
}
int trouverAuDessus(int noeud, int minimum)
{
for(int iPuissance = 19; iPuissance >= 1; iPuissance--)
{
if(petitGrand[0][noeud][iPuissance] >= minimum)
{
noeud += (1 << iPuissance-1);
}
}
return noeud;
}
int trouverEnDessous(int noeud, int maximum)
{
for(int iPuissance = 19; iPuissance >= 1; iPuissance--)
{
if(petitGrand[1][noeud][iPuissance] <= maximum)
{
noeud += (1 << iPuissance);
}
}
return noeud;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int nbVilles, nbChemins, nbQuestions;
cin >> nbVilles >> nbChemins >> nbQuestions;
int extreme;
for(int i = 0; i < nbChemins; i++)
{
int a, b;
cin >> a >> b;
chemins[a].push_back(b);
chemins[b].push_back(a);
}
if((nbVilles <= 3000) && (nbQuestions <= 3000) && (nbChemins <= 6000))
{
}
else
{
for(int i = 0; i < nbVilles; i++)
{
if(chemins[i].size() == 1)
{
extreme = i;
}
}
lister(extreme, 0, -1);
for(int i = nbVilles-1; i >= 0; i++)
{
petitGrand[0][i][0] = liste[i];
petitGrand[1][i][0] = liste[i];
for(int iValeur = 1; iValeur < 20; iValeur++)
{
if(i == nbVilles-1)
{
petitGrand[0][i][iValeur] = INFINI;
petitGrand[1][i][iValeur] = 0;
}
else
{
petitGrand[0][i][iValeur] = min(petitGrand[0][i+1][iValeur-1], petitGrand[0][i][iValeur-1]);
petitGrand[1][i][iValeur] = max(petitGrand[1][i+1][iValeur-1], petitGrand[1][i][iValeur-1]);
}
}
}
// construire(1, 0, nbVilles-1);
}
//cout << "ijlk" << endl;
for(int iQ = 1; iQ <= nbQuestions; iQ++)
{
if((nbVilles <= 3000) && (nbQuestions <= 3000) && (nbChemins <= 6000)/**/)
{
int deb, fin;
pair<int, int> interdit[2];
interdit[0].first = 0;
interdit[1].second = nbVilles;
cin >> deb >> fin >> interdit[0].second >> interdit[1].first;
interdit[1].first++;
vector<pair<int, int>> caseMaint;
vector<pair<int, int>> proCase;
proCase.push_back({deb, 0});
bool trouve = false;
while(proCase.size())
{
caseMaint = proCase;
proCase.clear();
for(auto situation : caseMaint)
{
int iVille = situation.first, humainLoup = situation.second;
if(dejaVu[iVille][humainLoup] == iQ) continue;
dejaVu[iVille][humainLoup] = iQ;
if((iVille >= interdit[humainLoup].first) && (iVille < interdit[humainLoup].second)) continue;
if((humainLoup == 1) && (iVille == fin))
{
trouve = true;
break;
}
if(humainLoup == 0)
proCase.push_back({iVille, 1});
for(int pro : chemins[iVille])
{
proCase.push_back({pro, humainLoup});
}
}
if(trouve)
{
break;
}
}
cout << trouve << "\n";
}
else
{
int deb, fin;
pair<int, int> autorise;
cin >> deb >> fin >> autorise.first >> autorise.second;
--deb;
--autorise.first;
--autorise.second;
--fin;
if(position[deb] > position[fin])
{
swap(deb, fin);
}
deb = position[deb];
fin = position[fin];
// cout << deb << " " << fin << endl;
//cout << deb << " " << fin << " : " << interdit[0].first << " " << interdit[0].second << " | " << interdit[1].first << " " << interdit[1].second << "\n";
// cout << "lkj" << endl;
deb = trouverAuDessus(deb, autorise.first);
//cout << deb << endl;
//deb = min(deb, fin - 1);
if(deb >= fin)
{
cout << 0 << "\n";
}
else
{
// cout << "lkj" << endl;
deb = trouverEnDessous(deb, autorise.second);
// cout << deb << endl;
//cout << "lkj" << endl;
if(deb >= fin)
{
cout << 1 << "\n";
}
else
cout << 0 << "\n";
}
}
}
}