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 |
|
|
|
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 |