| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 122258 |
2019-06-28T02:08:51 Z |
Retro3014 |
None (JOI16_ho_t3) |
C++17 |
|
203 ms |
17116 KB |
#include <bits/stdc++.h>
#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAX_N = 100000;
int N, M, Q;
vector<pair<pii, int> > edge;
vector<pii> gp[MAX_N+1];
int dist[MAX_N+1];
vector<pair<int, pii> > edge2;
priority_queue<pii> pq;
void dijk(){
pq.push({0, 1});
while(!pq.empty()){
int now = pq.top().second; pq.pop();
for(int i=0; i<gp[now].size(); i++){
if(gp[now][i].first==1) continue;
if(dist[gp[now][i].first] == 0 || dist[gp[now][i].first]==dist[now]+1){
if(dist[gp[now][i].first]==0){
pq.push({dist[gp[now][i].first], gp[now][i].first});
dist[gp[now][i].first] = dist[now]+1;
}
edge2.pb({gp[now][i].second, {now, gp[now][i].first}});
}
}
}
}
int group[MAX_N+1], num[MAX_N+1];
void init_g(){
for(int i=1; i<=N; i++){
group[i] = i; num[i] = 1;
}
}
int find_g(int x){
return (x==group[x])? x : group[x] = find_g(group[x]);
}
void union_g(int x, int y){
x = find_g(x); y = find_g(y);
if(x==y) return;
group[x] = y;
num[y]+=num[x];
}
vector<int> ans;
int cnt = 1;
vector<int> gp2[MAX_N+1];
bool chk[MAX_N+1];
void dfs(int x){
if(chk[x]) return;
chk[x] = true; cnt++;
for(int i=0; i<gp2[x].size(); i++){
dfs(gp2[x][i]);
}
}
void add(int x, int y){
gp2[x].pb(y);
if(chk[x]){
if(chk[y]) return;
dfs(y);
}
}
int main(){
scanf("%d%d%d", &N, &M, &Q);
for(int i=1; i<=M; i++){
int a, b;
scanf("%d%d", &a, &b);
edge.pb({{a, b}, Q+1});
}
for(int i=1; i<=Q; i++){
int x;
scanf("%d", &x);
edge[x-1].second = i;
}
for(int i=0; i<edge.size(); i++){
gp[edge[i].first.first].pb({edge[i].first.second, edge[i].second});
gp[edge[i].first.second].pb({edge[i].first.first, edge[i].second});
}
dijk();
sort(edge2.begin(), edge2.end());
/*for(int i=0; i<edge2.size(); i++){
printf("%d %d\n", edge2[i].second.first, edge2[i].second.second);
}*/
//init_g();
chk[1] = true;
for(int i=Q; i>=1; i--){
while(!edge2.empty() && edge2.back().first>i){
add(edge2.back().second.first, edge2.back().second.second);
edge2.pop_back();
}
ans.pb(N-cnt);
}
while(!ans.empty()){
printf("%d\n", ans.back());
ans.pop_back();
}
return 0;
}
Compilation message
2016_ho_t3.cpp: In function 'void dijk()':
2016_ho_t3.cpp:38:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<gp[now].size(); i++){
~^~~~~~~~~~~~~~~
2016_ho_t3.cpp: In function 'void dfs(int)':
2016_ho_t3.cpp:79:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<gp2[x].size(); i++){
~^~~~~~~~~~~~~~
2016_ho_t3.cpp: In function 'int main()':
2016_ho_t3.cpp:104:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<edge.size(); i++){
~^~~~~~~~~~~~
2016_ho_t3.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &N, &M, &Q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
2016_ho_t3.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~
2016_ho_t3.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
203 ms |
17116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
