LeetCode Weekly Contest 155 4問目 - Sort Items by Groups Respecting Dependencies [1203]

Source

LeetCode Weekly Contest 155
問題文

問題概要

省略

解法

省略

cLay（version 20190921-1）のコード

C++に変換後のコードはこちら

#define main dummy_main
{}
#undef main

graph g;

int gn[3d4], gi[3d4];
vector<int> gnode[6d4];
int gs[6d4];
vector<int> A, B, pA[6d4], pB[6d4];
int M, tA[1d6], tB[1d6];
int tmparr[1d6], ts[6d4];

class Solution {
public:
  vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
    dummy_main();

    int i, j, k, x;
    vector<int> res;
    
    rep(i,n) if(group[i]==-1) group[i] = m++;

    A.clear();
    B.clear();
    rep(i,m) pA[i].clear();
    rep(i,m) pB[i].clear();

    rep(i,m) gs[i] = 0;
    rep(i,m) gnode[i].clear();
    
    rep(i,n){
      j = group[i];
      gn[i] = j;
      gi[i] = gs[j]++;
      gnode[j].push_back(i);
    }

    rep(i,n) rep(j,beforeItems[i].size()){
      k = beforeItems[i][j];
      if(gn[i]==gn[k]){
        x = gn[i];
        pA[x].push_back(gi[k]);
        pB[x].push_back(gi[i]);
      } else {
        A.push_back(gn[k]);
        B.push_back(gn[i]);
      }
    }

    rep(k,m){
      M = 0;
      rep(i,pA[k].size()) tA[M] = pA[k][i], tB[M++] = pB[k][i];
      g.setDirectEdge(gs[k], M, tA, tB);
      i = g.TopologicalSort(ts);
      if(i==0) return res;
      rep(i,gs[k]) tmparr[i] = gnode[k][i];
      rep(i,gs[k]) gnode[k][i] = tmparr[ts[i]];
    }

    M = 0;
    rep(i,A.size()) tA[M] = A[i], tB[M++] = B[i];
    g.setDirectEdge(m, M, tA, tB);
    i = g.TopologicalSort(ts);
    if(i==0) return res;
    rep(i,m){
      x = ts[i];
      rep(j,gs[x]) res.push_back(gnode[x][j]);
    }
    return res;
  }
};

Current time: 2024年04月26日08時10分34秒
Last modified: 2019年09月22日20時10分59秒 (by laycrs)
Tags: Competitive_Programming_Incomplete LeetCode
トップページに戻る

Logged in as: unknown user (not login)