Submission #2526470
Source Code Expand
#include <stack>
#include <queue>
#include <cstdio>
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <string>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,n0,n) for(int i=n0;i<n;i++)
#define Com(i,j,n) for(int i=0;i<n-1;i++)for(int j=i+1;j<n;j++)
#define INF (1<<29)
#define test cout << "test" << endl;
int unionf[100010];
int ranks[100010];
int init(int a){
rep(i,a){
unionf[i+1]=i+1;
ranks[i+1]=1;
}
}
int find(int a){
return (unionf[a]==a)? a:unionf[a]=find(unionf[a]);
}
void unite(int a,int b){
a=find(a);
b=find(b);
if(ranks[a]>ranks[b]){
unionf[b]=a;
}
else {
unionf[a]=b;
if(ranks[a]==ranks[b])
ranks[b]++;
}
return ;
}
int main (){
int NNN,MMM;
cin >> NNN >> MMM;
vector <pair<int,pair<int,int>>> bridges;
vector <pair<int,pair<int,int>>> people;
pair <int ,int > tempair;
int tempa,tempb;
int tempyear;
rep(i,MMM){
cin >> tempa >> tempb >>tempyear;
tempair = make_pair(tempa,tempb);
bridges.push_back(make_pair(tempyear,tempair));
}
sort(bridges.begin(),bridges.end());
int QQQ;
cin >> QQQ;
rep(i,QQQ){
cin >> tempa >>tempyear;
tempair = make_pair(i,tempa);
people.push_back(make_pair(tempyear,tempair));
}
sort(people.begin(),people.end());
int answers[QQQ+1];
int year_people; // 今都市数を数えたい人の番号(入力の順番)
int year_bridges;//今年を数えたい人の許容年
int number_of_people; //
int toshi_people;
int count_toshi;
int loop_people=people.size()-1;
int loop_bridges=bridges.size()-1;
bool bridge_check=true;
init(NNN);
while(1){
year_people = people[loop_people].first;
number_of_people = people[loop_people].second.first;
toshi_people = people[loop_people].second.second;
// cout << "year_people =" << year_people << "number_of_people =" <<number_of_people <<"toshi_people =" <<toshi_people <<endl;
while(1){
year_bridges = bridges[loop_bridges].first;
// cout << year_bridges <<endl;
if(year_bridges >year_people){
unite(bridges[loop_bridges].second.first,bridges[loop_bridges].second.second);
// cout <<bridges[loop_bridges].second.first <<" " <<bridges[loop_bridges].second.second <<endl;
loop_bridges --;
}
else{
break;
}
if(loop_bridges<0) break;
}
count_toshi=0;
rep(i,NNN){
if(find(unionf[i+1])==find(toshi_people)){
count_toshi++;
}
}
answers[number_of_people]=count_toshi;
loop_people--;
if(loop_people<0) break;
}
rep(i,QQQ){
cout << answers[i] << endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 道路の老朽化対策について |
User |
k_karen |
Language |
C++14 (GCC 5.4.1) |
Score |
50 |
Code Size |
2716 Byte |
Status |
TLE |
Exec Time |
2104 ms |
Memory |
6896 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
All |
Score / Max Score |
0 / 0 |
50 / 50 |
0 / 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 |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
1 ms |
256 KB |
subtask1_01.txt |
AC |
9 ms |
256 KB |
subtask1_02.txt |
AC |
9 ms |
256 KB |
subtask1_03.txt |
AC |
9 ms |
256 KB |
subtask1_04.txt |
AC |
6 ms |
256 KB |
subtask1_05.txt |
AC |
9 ms |
256 KB |
subtask1_06.txt |
AC |
10 ms |
256 KB |
subtask1_07.txt |
AC |
9 ms |
256 KB |
subtask2_01.txt |
TLE |
2104 ms |
6512 KB |
subtask2_02.txt |
TLE |
2104 ms |
6512 KB |
subtask2_03.txt |
TLE |
2104 ms |
6640 KB |
subtask2_04.txt |
TLE |
2104 ms |
6512 KB |
subtask2_05.txt |
TLE |
2103 ms |
3700 KB |
subtask2_06.txt |
TLE |
2104 ms |
6512 KB |
subtask2_07.txt |
TLE |
2104 ms |
6512 KB |
subtask2_08.txt |
TLE |
2104 ms |
6512 KB |
subtask2_09.txt |
TLE |
2104 ms |
6512 KB |
subtask2_10.txt |
TLE |
2104 ms |
6512 KB |
subtask2_11.txt |
TLE |
2104 ms |
6896 KB |
subtask2_12.txt |
TLE |
2104 ms |
6512 KB |