LeetCode Biweekly Contest 13 2問目 - Smallest Common Region [1257]

Source

LeetCode Biweekly Contest 13
問題文

問題概要

省略

解法

省略

cLay（version 20191123-1）のコード

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

#define main dummy_main
{}
#undef main

map<string,int> mp;
string node[2d5];
int N, M, A[2d5], B[2d5];
int vis[2d5];

int getNode(string s){
  if(mp.count(s)) return mp[s];
  node[N] = s;
  mp[s] = N;
  return N++;
}

class Solution {
public:
  string findSmallestRegion(vector<vector<string>>& regions, string region1, string region2) {
    int a, b, x, y;
    graph g;
    dummy_main();

    N = M = 0;
    mp.clear();
    rep(i,regions.size()){
      a = getNode(regions[i][0]);
      rep(j,1,regions[i].size()){
        b = getNode(regions[i][j]);
        arrInsert(M,M,A,b,B,a);
      }
    }
    x = getNode(region1);
    y = getNode(region2);

    g.setDirectEdge(N,M,A,B);
    rep(i,N) vis[i] = 0;
    a = x;
    for(;;){
      vis[a] = 1;
      if(g.es[a]==0) break;
      a = g.edge[a][0];
    }
    b = y;
    for(;;){
      if(vis[b]) break;
      b = g.edge[b][0];
    }
    return node[b];
  }
};

Current time: 2024年04月26日18時51分03秒
Last modified: 2019年11月23日18時28分28秒 (by laycrs)
Tags: Competitive_Programming_Incomplete LeetCode
トップページに戻る

Logged in as: unknown user (not login)