Submission #1245414


Source Code Expand

#include <iostream>
#include <queue>
#include <algorithm>
#include <map>

using namespace std;

int N, M, Q;
int p[100000];
int S[100000];
int ans[100000];


struct road {
  int y,s,t;

  
  road () {}
  road (int yy, int ss, int tt) : y(yy), s(ss), t(tt) {}

  bool operator < (const road &oth) const {
    if(y != oth.y) return y < oth.y;
    if(s != oth.s) return s < oth.s;
    return t < oth.t;
  }
};

vector<road> q;

void makeset (int n) {
  for(int i = 0; i < n; i++) {
    p[i] = i;
    S[i] = 1;
  }
}

int  find (int x) {
  return p[x] == x ? x : p[x] = find(p[x]);
}

bool same(int x, int y) {
  return find(x) == find(y);
}

void Union(int x, int y) {
  if(!same(x,y)) { 
    S[y] += S[x];
    p[x] = y;
  }
}

int main() {
  cin >> N >> M;

  priority_queue<road> pq;

  for(int i = 0; i < M; i++) {
    int a, b, y;
    cin >> a >> b >> y;
    a--; b--;
    pq.push(road(y,a,b));
  }
  
  
  cin >> Q;

  for(int i = 0; i < Q; i++) {
    int v, w;
    cin >> v >> w;
    v--;
    q.push_back(road(w,v,i));
  }
  sort(q.begin(),q.end());
  reverse(q.begin(),q.end());

  makeset(N);

  
  for(int i = 0; i < Q; i++) {
    while(!pq.empty() && q[i].y < pq.top().y) {
      Union(find(pq.top().s),find(pq.top().t));
      /* for(int i = 0; i < N; i++) {
	cout <<" S["<<i<<"] = "<<S[i]<<endl;
	}*/
      pq.pop();
    }
    ans[q[i].t] = S[find(q[i].s)];
  }

  for(int i = 0; i < Q; i++) {
    cout << ans[i] << endl;
  }
}


  
  


  

Submission Info

Submission Time
Task D - 道路の老朽化対策について
User shossie1016
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1550 Byte
Status AC
Exec Time 446 ms
Memory 7536 KB

Judge Result

Set Name Sample Subtask1 All
Score / Max Score 0 / 0 50 / 50 50 / 50
Status
AC × 3
AC × 10
AC × 22
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt
All sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt
Case Name Status Exec Time Memory
sample_01.txt AC 6 ms 764 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
subtask1_01.txt AC 5 ms 256 KB
subtask1_02.txt AC 5 ms 256 KB
subtask1_03.txt AC 5 ms 256 KB
subtask1_04.txt AC 4 ms 256 KB
subtask1_05.txt AC 5 ms 256 KB
subtask1_06.txt AC 5 ms 256 KB
subtask1_07.txt AC 5 ms 256 KB
subtask2_01.txt AC 430 ms 6896 KB
subtask2_02.txt AC 425 ms 6896 KB
subtask2_03.txt AC 434 ms 6896 KB
subtask2_04.txt AC 443 ms 6896 KB
subtask2_05.txt AC 299 ms 3956 KB
subtask2_06.txt AC 413 ms 7024 KB
subtask2_07.txt AC 420 ms 7024 KB
subtask2_08.txt AC 420 ms 7536 KB
subtask2_09.txt AC 446 ms 6896 KB
subtask2_10.txt AC 442 ms 7536 KB
subtask2_11.txt AC 440 ms 6768 KB
subtask2_12.txt AC 431 ms 7024 KB