Submission #63113

#	Time	Username	Problem	Language	Result	Execution time	Memory
63113		Arturgo	Port Facility (JOI17_port_facility)	C++14	78 / 100	2162 ms	525844 KiB

port_facility

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstdio>
using namespace std;

const int MOD = 1000000007;

struct Inter {
  int deb, fin, id;
  Inter(int _deb = 0, int _fin = 0, int _id = 0) {
    deb = _deb;
    fin = _fin;
    id = _id;
  }
};

bool operator < (const Inter &a, const Inter &b) {
  return a.deb < b.deb;
}

struct Noeud {
  int g, d;
  int inter;
  short couleur;
  int parent;
  bool aSous;
  Noeud() {
    g = d = inter = couleur = parent = -1;
    aSous = false;
  }
};

int nbNoeuds = 0;
Noeud noeuds[16 * 1000 * 1000];
int arbre_deb, arbre_fin;

void colorie_fils(int noeud, short couleur, vector<int>& coloured) {
  if(noeuds[noeud].couleur != -1) {
    if(couleur != noeuds[noeud].couleur && noeuds[noeud].aSous) {
      printf("0\n");
      exit(0);
      return;
    }
    return;
  }

  noeuds[noeud].couleur = couleur;

  if(noeuds[noeud].inter != -1) {
    coloured.push_back(noeuds[noeud].inter);
  }
  
  if(noeuds[noeud].g != -1) {
    colorie_fils(noeuds[noeud].g, couleur, coloured);
  }
  if(noeuds[noeud].d != -1) {
    colorie_fils(noeuds[noeud].d, couleur, coloured);
  }

  if(noeuds[noeud].parent != -1) {
    colorie_fils(noeuds[noeud].parent, couleur, coloured);
  }
}

int nbInters;
vector<vector<int>> entreesDeb, entreesFin;
vector<int> sortiesDeb, sortiesFin;

const int NB_LEAVES = (1 << 18);

int ajoute_noeud(int noeud, int deb, int fin, vector<int>& action, bool copy = true, int d = 0, int f = NB_LEAVES) {
  if(deb >= f || fin <= d)
    return noeud;
  if(deb <= d && f <= fin) {
    if(copy) {
      Noeud nouv = noeuds[noeud];
      nouv.parent = noeud;
      noeuds[nbNoeuds++] = nouv;
      action.push_back(nbNoeuds - 1);
      return nbNoeuds - 1;
    }
    else {
      action.push_back(noeud);
      return noeud;
    }
  }
  int m = (d + f) / 2;
  int dg = ajoute_noeud(noeuds[noeud].g, deb, fin, action, copy, d, m);
  int dd = ajoute_noeud(noeuds[noeud].d, deb, fin, action, copy, m, f);
  if(copy) {
    Noeud nouv;
    nouv.g = dg;
    nouv.d = dd;
    nouv.aSous = noeuds[dg].aSous || noeuds[dd].aSous;
    nouv.parent = noeud;
    noeuds[nbNoeuds++] = nouv;
    return nbNoeuds - 1;
  }
  else {
    noeuds[noeud].aSous = noeuds[dg].aSous || noeuds[dd].aSous;
    return noeud;
  }
}

int gen_prof(int prof) {
  if(prof == 0) {
    return nbNoeuds++;
  }

  int g = gen_prof(prof - 1);
  int d = gen_prof(prof - 1);
  noeuds[nbNoeuds].g = g;
  noeuds[nbNoeuds].d = d;
  return nbNoeuds++;
}

void gen_arbre(vector<Inter>& inters, int& racine, vector<vector<int>>& entrees, vector<int>& sorties) {
  sort(inters.begin(), inters.end());

  entrees = vector<vector<int>>(nbInters, vector<int>());
  sorties = vector<int>(nbInters, 0);

  racine = gen_prof(18);

  for(Inter inter : inters) {
    vector<int> modifs;
    racine = ajoute_noeud(racine, inter.deb, inter.fin, modifs);
    for(int noeud : modifs) {
      entrees[inter.id].push_back(noeud);
    }
    
    modifs.clear();
    racine = ajoute_noeud(racine, inter.fin - 1, inter.fin, modifs);

    for(int noeud : modifs) {
      noeuds[noeud].aSous = true;
    }

    modifs.clear();
    racine = ajoute_noeud(racine, inter.fin - 1, inter.fin, modifs, false);

    for(int noeud : modifs) {
      noeuds[noeud].inter = inter.id;
      sorties[inter.id] = noeud;
    }
  }
}

int main() {
  scanf("%d", &nbInters);
  
  vector<Inter> inters_deb, inters_fin;
  for(int iInter = 0;iInter < nbInters;iInter++) {
    int deb, fin;
    scanf("%d%d", &deb, &fin);

    inters_deb.push_back(Inter(deb - 1, fin - 1, iInter));
    inters_fin.push_back(Inter(2 * nbInters - fin, 2 * nbInters - deb, iInter));
  }

  gen_arbre(inters_deb, arbre_deb, entreesDeb, sortiesDeb);
  gen_arbre(inters_fin, arbre_fin, entreesFin, sortiesFin);

  int nbSolutions = 1;

  vector<int> couleurs(nbInters, -1);
  for(int iInter = 0;iInter < nbInters;iInter++) {
    if(noeuds[sortiesDeb[iInter]].couleur == -1 && noeuds[sortiesFin[iInter]].couleur == -1) {
      nbSolutions = 2 * nbSolutions % MOD;
      
      short couleur = 0;
      vector<int> doit_colorier;
      doit_colorier.push_back(iInter);

      noeuds[sortiesDeb[iInter]].couleur = noeuds[sortiesFin[iInter]].couleur = couleur ^ 1;

      while(!doit_colorier.empty()) {
	vector<int> voisins;
	for(int inter : doit_colorier) {
	  for(int entree : entreesDeb[inter]) {
	    colorie_fils(entree, couleur, voisins);
	  }
	  for(int entree : entreesFin[inter]) {
	    colorie_fils(entree, couleur, voisins);
	  }
	}
	
	couleur = couleur ^ 1;

	doit_colorier = voisins;
      }
    }
    if(noeuds[sortiesDeb[iInter]].couleur != -1 && noeuds[sortiesFin[iInter]].couleur != -1) {
      if(noeuds[sortiesDeb[iInter]].couleur != noeuds[sortiesFin[iInter]].couleur) {
        printf("\n");
	exit(0);
      }
    }
  }

  printf("%d\n", nbSolutions);
  return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:152:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &nbInters);
   ~~~~~^~~~~~~~~~~~~~~~~
port_facility.cpp:157:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &deb, &fin);
     ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 56 / 56
• Subtask 4: 0 / 22