Submission #1302912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302912		sano	World Map (IOI25_worldmap)	C++20	86 / 100	586 ms	6432 KiB

worldmap

#include "worldmap.h"
#include <iostream>
#include <set>
#define vec vector
#define For(i, n) for(int i = 0; i < (int)n; i++)
using namespace std;

vec<vec<int>> g;
vec<int> bol;
vec<int> o;
vec<vec<int>> boc;
vec<int> vrst;

void dfs(int x, vec<int>&p, int pr = -1){
  bol[x] = 1;
  p.push_back(x);
  for(auto i : g[x]){
    if(i == pr) continue;
    if(bol[i]) {
      if(vrst[i] < vrst[x]) boc[i].push_back(x);
      continue;
    }
    vrst[i] = vrst[x] + 1;
    o[i] = x;
    dfs(i, p, x);
    p.push_back(x);
  }
  return;
}

void vypis(vec<int>&p){
  for(auto i : p){
    cerr << i << ' ';
  }
  cerr << endl;
  return;
}

vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
  vec<vec<int>> odp;
  g.clear();
  bol.clear();
  o.clear();
  boc.clear();
  vrst.clear();
  g.resize(N);
  bol.resize(N, false);
  vrst.resize(N, 0);
  o.resize(N, -1);
  boc.resize(N);
  cerr << "cvok" << endl;
  For(i, M){
    int a, b; a = A[i], b = B[i]; a--; b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  cerr << "cvok" << endl;
  vec<int> p;
  dfs(0, p);
  vec<int> deti(N, 0);
  cerr << "cvok" << endl;
  For(i, N){
    if(o[i] == -1) continue;
    deti[o[i]]++;
  }
  vec<int> prec;
  odp.push_back(p);
  cerr << "cvok" << endl;
  for(;;){
    set<int> vym;
    bool koniec = 0;
    vypis(p);
    cerr << "deti: "; vypis(deti);
    For(i, p.size()){
      if(deti[p[i]] == 0) {
        cerr << "som tu: " << i << endl;
        vym.insert(p[i]);
        cerr << "ok" << endl;
        if(p[i] == 0){
          koniec = 1;
          break;
        }
        p[i] = o[p[i]];
      }
    }
    if(koniec) {cerr << "tu " << endl; break;}
    for(auto i : vym){
      deti[o[i]]--;
    }
    vec<int> vp = p;
    //tu ries tie spatne dfs hrany
    For(i, vp.size()){
      if(deti[vp[i]] == 0 && i != 0 && vp[i-1] == vp[i] && !boc[vp[i]].empty()) {
        int pvp = vp[i];
        vp[i] = boc[pvp].back();
        boc[pvp].pop_back(); 
      }
    }

    //koniec spatnych hran ostatne funguje
    odp.push_back(p);
    odp.push_back(vp);
    odp.push_back(p);
    cerr << "vym: "; for(auto i : vym) cerr << i << ' ';
    cerr << endl;
    
  }
  if(odp.size() > p.size()){
    int os = odp.size();
    For(i, odp.size()){
      odp[i].resize(os, 0);
    }
  }
  if(p.size() > odp.size()){
    int ps = p.size(), os = odp.size();

    For(i, ps - os){
      odp.push_back(p);
    }
  }
  cerr << "koncim" << endl;
  For(i, odp.size()){
    For(j, odp[i].size()){
      odp[i][j]++;
    }
  }
  return odp;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8
• Subtask 5: 14 / 14
• Subtask 6: 42 / 56