| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 348549 |
2021-01-15T07:44:38 Z |
arnold518 |
Link (CEOI06_link) |
C++14 |
|
720 ms |
87208 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 5e5;
int N, K;
int A[MAXN+10];
vector<int> adj[MAXN+10];
int deg[MAXN+10];
int col[MAXN+10];
int vis[MAXN+10], cyc[MAXN+10];
int dep[MAXN+10];
vector<int> V[MAXN+10];
void dfs(int now, int bef, int d)
{
dep[now]=d;
for(int nxt : adj[now])
{
if(nxt==bef) continue;
if(cyc[nxt]) continue;
dfs(nxt, now, d+1);
}
}
int par[MAXN+10][30];
int main()
{
scanf("%d%d", &N, &K);
for(int i=1; i<=N; i++)
{
int u, v;
scanf("%d%d", &u, &v);
A[u]=v;
adj[v].push_back(u);
deg[v]++;
}
for(int i=1; i<=N; i++)
{
if(vis[i]) continue;
int now=i;
vector<int> S;
while(1)
{
vis[now]=i;
S.push_back(now);
if(vis[A[now]])
{
if(vis[A[now]]!=i) break;
while(!S.empty() && S.back()!=A[now])
{
V[i].push_back(S.back());
cyc[S.back()]=i;
S.pop_back();
}
V[i].push_back(A[now]);
cyc[A[now]]=i;
break;
}
now=A[now];
}
}
for(int i=1; i<=N; i++) if(cyc[i])
{
dfs(i, i, 1);
}
//for(int i=1; i<=N; i++) printf("%d ", dep[i]); printf("\n");
priority_queue<pii> PQ;
int now=1;
for(int i=1; i<=K+1; i++)
{
if(col[now]==0)
{
deg[A[now]]--;
}
col[now]=1;
now=A[now];
}
for(int i=1; i<=N; i++) if(deg[i]==0 && col[i]==0 && !cyc[i]) PQ.push({dep[i], i});
int ans=0;
while(!PQ.empty())
{
int now=PQ.top().second; PQ.pop();
if(deg[now]!=0) continue;
if(col[now]) continue;
if(cyc[now]) continue;
ans++;
//printf("%d\n", now);
int u=now;
for(int i=1; i<=K; i++)
{
if(col[u]==0)
{
deg[A[u]]--;
if(!cyc[A[u]] && deg[A[u]]==0 && !col[A[u]]) PQ.push({dep[A[u]], A[u]});
}
col[u]=1;
u=A[u];
}
}
for(int i=1; i<=N; i++) if(!cyc[i]) assert(col[i]);
for(int i=1; i<=N; i++)
{
if(V[i].empty()) continue;
int L=V[i].size();
vector<int> VV;
for(int j=0; j<V[i].size(); j++) if(!col[V[i][j]]) VV.push_back(j);
for(int j=0; j<V[i].size(); j++) if(!col[V[i][j]]) VV.push_back(j+L);
for(int j=0; j<V[i].size(); j++) if(!col[V[i][j]]) VV.push_back(j+L+L);
if(VV.empty()) continue;
if(K>=L)
{
ans++;
continue;
}
int S=VV.size()/3;
for(int i=0; i<S+S; i++) par[i][0]=lower_bound(VV.begin(), VV.end(), VV[i]+K)-VV.begin();
for(int i=S+S; i<S+S+S; i++) par[i][0]=-1;
for(int i=1; i<=20; i++) for(int j=0; j<S+S+S; j++)
{
if(par[j][i-1]==-1) par[j][i]=-1;
else par[j][i]=par[par[j][i-1]][i-1];
}
int nans=987654321;
for(int i=0; i<S; i++)
{
int now=i, val=1;
for(int j=20; j>=0; j--)
{
if(par[now][j]!=-1 && VV[par[now][j]]<VV[i]+L)
{
now=par[now][j];
val+=(1<<j);
}
}
nans=min(nans, val);
}
ans+=nans;
}
//for(int i=1; i<=N; i++) assert(col[i]);
printf("%d\n", ans);
}
Compilation message
link.cpp: In function 'int main()':
link.cpp:123:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
123 | for(int j=0; j<V[i].size(); j++) if(!col[V[i][j]]) VV.push_back(j);
| ~^~~~~~~~~~~~
link.cpp:124:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | for(int j=0; j<V[i].size(); j++) if(!col[V[i][j]]) VV.push_back(j+L);
| ~^~~~~~~~~~~~
link.cpp:125:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
125 | for(int j=0; j<V[i].size(); j++) if(!col[V[i][j]]) VV.push_back(j+L+L);
| ~^~~~~~~~~~~~
link.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
35 | scanf("%d%d", &N, &K);
| ~~~~~^~~~~~~~~~~~~~~~
link.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
39 | scanf("%d%d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23916 KB |
Output is correct |
| 2 |
Correct |
14 ms |
23916 KB |
Output is correct |
| 3 |
Correct |
15 ms |
23916 KB |
Output is correct |
| 4 |
Correct |
16 ms |
24172 KB |
Output is correct |
| 5 |
Correct |
17 ms |
24172 KB |
Output is correct |
| 6 |
Correct |
33 ms |
27884 KB |
Output is correct |
| 7 |
Correct |
45 ms |
28520 KB |
Output is correct |
| 8 |
Correct |
63 ms |
31856 KB |
Output is correct |
| 9 |
Correct |
102 ms |
42772 KB |
Output is correct |
| 10 |
Correct |
97 ms |
38412 KB |
Output is correct |
| 11 |
Correct |
226 ms |
81320 KB |
Output is correct |
| 12 |
Correct |
191 ms |
37636 KB |
Output is correct |
| 13 |
Correct |
285 ms |
57948 KB |
Output is correct |
| 14 |
Correct |
348 ms |
59232 KB |
Output is correct |
| 15 |
Correct |
472 ms |
73524 KB |
Output is correct |
| 16 |
Correct |
510 ms |
80240 KB |
Output is correct |
| 17 |
Correct |
628 ms |
82440 KB |
Output is correct |
| 18 |
Correct |
682 ms |
69948 KB |
Output is correct |
| 19 |
Correct |
665 ms |
74024 KB |
Output is correct |
| 20 |
Correct |
665 ms |
78132 KB |
Output is correct |
| 21 |
Correct |
677 ms |
87208 KB |
Output is correct |
| 22 |
Correct |
679 ms |
86324 KB |
Output is correct |
| 23 |
Correct |
655 ms |
86224 KB |
Output is correct |
| 24 |
Correct |
720 ms |
86088 KB |
Output is correct |
| 25 |
Correct |
691 ms |
85484 KB |
Output is correct |
