結果

問題 No.529 帰省ラッシュ
ユーザー Y17Y17
提出日時 2019-04-03 02:05:13
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 761 ms / 4,500 ms
コード長 5,778 bytes
コンパイル時間 1,718 ms
コンパイル使用メモリ 172,420 KB
実行使用メモリ 51,384 KB
最終ジャッジ日時 2024-05-08 22:12:42
合計ジャッジ時間 11,108 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 12 ms
27,776 KB
testcase_01 AC 12 ms
27,776 KB
testcase_02 AC 11 ms
27,648 KB
testcase_03 AC 11 ms
27,776 KB
testcase_04 AC 19 ms
27,904 KB
testcase_05 AC 19 ms
27,776 KB
testcase_06 AC 19 ms
27,904 KB
testcase_07 AC 19 ms
27,776 KB
testcase_08 AC 586 ms
41,344 KB
testcase_09 AC 553 ms
40,804 KB
testcase_10 AC 593 ms
41,776 KB
testcase_11 AC 582 ms
41,828 KB
testcase_12 AC 474 ms
40,960 KB
testcase_13 AC 383 ms
51,384 KB
testcase_14 AC 522 ms
45,184 KB
testcase_15 AC 761 ms
42,824 KB
testcase_16 AC 756 ms
42,956 KB
testcase_17 AC 595 ms
49,400 KB
testcase_18 AC 602 ms
49,652 KB
testcase_19 AC 609 ms
47,696 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int> > bridge;
vector<int> graph[100010];
pair<int, int> edge[200010];

int pre[100010];
int low[100010];
int com[100010];
int n, m;
int visited_cnt = 0;

int dis_dfs(int idx, int from){
    pre[idx] = visited_cnt;
    visited_cnt++;
    low[idx] = pre[idx];

    for(int i = 0;i < graph[idx].size();i++){
        int to = graph[idx][i];
        if(pre[to] == -1){
            low[idx] = min(low[idx], dis_dfs(to, idx));
        }else{
            if(from != to){
                low[idx] = min(low[idx], low[to]);
            }
        }
    }

    return low[idx];
}

vector<int> subGraph[100010];
vector<int> treeGraph[100010];

void make_dis_pair(int idx, int num){
    com[idx] = num;
    for(int i = 0;i < subGraph[idx].size();i++){
        if(com[subGraph[idx][i]] == -1){
            make_dis_pair(subGraph[idx][i], num);
        }
    }
    return;
}

int disGraph(){
    memset(pre, -1, sizeof(pre));
    memset(low, -1, sizeof(low));

    dis_dfs(0, -1);

    for(int i = 0;i < m;i++){
        int fi = edge[i].first;
        int se = edge[i].second;
        if(pre[fi] < low[se] || pre[se] < low[fi]){
            bridge.push_back(make_pair(min(fi, se), max(se, fi)));
        }else{
            subGraph[fi].push_back(se);
            subGraph[se].push_back(fi);
        }
    }

    memset(com, -1, sizeof(com));
    int pnum = 0;

    for(int i = 0;i < n;i++){
        if(com[i] == -1){
            make_dis_pair(i, pnum);
            pnum++;
        }
    }

    for(int i = 0;i < bridge.size();i++){
        int fi = bridge[i].first;
        int se = bridge[i].second;
        treeGraph[com[fi]].push_back(com[se]);
        treeGraph[com[se]].push_back(com[fi]);
    }

    return pnum;
}

class SegmentTree{
public:
  int Size;
  pair<int, int> Tree[1000000];

  void init(int n){
    Size = 1;
    while(Size < n) Size *= 2;

    for(int i = 0;i < Size;i++){
      if(i < n){
            Tree[Size-1+i] = make_pair(-1, i);
      }else{
            Tree[Size-1+i] = make_pair(-2, 0);
      }
    }

    for(int i = Size-2;i >= 0;i--){
      Tree[i] = max(Tree[i*2+1], Tree[i*2+2]);
    }
    return;
  }

  void update(int i, int num){
      int idx = Size-1+i;
      Tree[idx] = make_pair(num, i);

      while(idx > 0){
          idx = (idx-1)/2;
          Tree[idx] = max(Tree[idx*2+1], Tree[idx*2+2]);
      }
  }

  pair<int, int> get_max(int a, int b, int l, int r, int k){
    if(r <= a || b <= l) return make_pair(-1, 0);
    if(a <= l && r <= b) return Tree[k];

    return max(get_max(a, b, l, (l+r)/2, 2*k+1), get_max(a, b, (l+r)/2, r, 2*k+2));
  }

  pair<int, int> getmax(int a, int b){
    return get_max(a, b, 0, Size, 0);
  }
};

#define swap(i,j) { int tmp = i; i = j; j = tmp; }

vector<int> tree[100010];
vector<int> subtree[100010];

int par[100010] = {};
int num[100010] = {};
int vid[100010];
int nid[100010];
int head[100010];
int team[100010];
int size[100010] = {};
int b = 0;
bool used[100010] = {};

SegmentTree segTree;

void maketree(int i){
  used[i] = true;
  for(int x = 0;x < treeGraph[i].size();x++){
    if(!used[treeGraph[i][x]]){
      par[treeGraph[i][x]] = i;
      tree[i].push_back(treeGraph[i][x]);
      maketree(treeGraph[i][x]);
    }
  }
}

int setnum(int i){
  int ret = 1;
  for(int x = 0;x < tree[i].size();x++){
    ret += setnum(tree[i][x]);
  }

  return num[i] = ret;
}

void dis(int n){
  memset(team,-1,sizeof(team));

  priority_queue<pair<int, int> > que;

  for(int i = 0;i < n;i++){
    que.push(make_pair(num[i], i));
  }

  int gnum = 0;
  int next;
  int pos = 0;
  int i;
  while(!que.empty()){
    i = que.top().second; que.pop();
    if(team[i] != -1) continue;
    team[i] = gnum;
    size[gnum]++;
    subtree[gnum].push_back(i);
    nid[i] = 0;
    int nn = 1;
    head[i] = i;
    vid[i] = pos;
    pos++;
    next = i;
    while(tree[next].size() != 0){
      int maxi = 0;
      for(int j = 1;j < tree[next].size();j++){
        if(num[tree[next][maxi]] < num[tree[next][j]]){
          maxi = j;
        }
      }
      subtree[gnum].push_back(tree[next][maxi]);
      team[tree[next][maxi]] = gnum;
      head[tree[next][maxi]] = i;
      vid[tree[next][maxi]] = pos;
      nid[tree[next][maxi]] = nn;
      size[gnum]++;
      pos++;
      nn++;
      next = tree[next][maxi];
    }
    gnum++;
  }
  return;
}

long long subDist[100010];

void build(int n){
  maketree(0);
  setnum(0);
  dis(n);

  segTree.init(n);

  return;
}

pair<int, int> getMax(int i, int j){
  if(vid[i] > vid[j]) swap(i, j);
  if(head[i] == head[j]) return segTree.getmax(vid[i], vid[j]+1);
  return max(getMax(i, par[head[j]]), segTree.getmax(vid[head[j]], vid[j]+1));
}

priority_queue<int> que[100010];

int main(){
    int q;
    cin >> n >> m >> q;

    for(int i = 0;i < m;i++){
        cin >> edge[i].first >> edge[i].second;
        edge[i].first--, edge[i].second--;
        graph[edge[i].first].push_back(edge[i].second);
        graph[edge[i].second].push_back(edge[i].first);
    }

    int n2 = disGraph();
    build(n2);

    int query, u, v;
    for(int p = 0;p < q;p++){
        cin >> query >> u >> v;
        if(query == 1){
            u--;
            que[vid[com[u]]].push(v);
            segTree.update(vid[com[u]], que[vid[com[u]]].top());
        }else{
            u--, v--;
            pair<int, int> tmp;
            tmp = getMax(com[u], com[v]);
            cout << tmp.first << endl;
            if(tmp.first != -1){
                que[tmp.second].pop();
                if(que[tmp.second].size() == 0){
                    segTree.update(tmp.second, -1);
                }else{
                    segTree.update(tmp.second, que[tmp.second].top());
                }
            }
        }
    }

    return 0;
}
0