3143 | 2023. 02. 20 11:18:45 | renn | Hálózatjavítás | cpp17 | Időlimit túllépés 4/50 | 400ms | 6520 KiB |
#include <bits/stdc++.h>
using namespace std;
#define GOTTAGOFAST cin.tie(0); ios::sync_with_stdio(0);
vector<int> szin;
stack<int> path;
stack<int> temp;
bool jo = false;
map<pair<int, int>, int> vonalak;
int maxc = 0;
void bejar(vector<vector<int>>& graf, int& n, int c)
{
szin[c] = 1;
path.push(c);
for(int& x : graf[c])
{
if(szin[x] == 1) // kört találtam
{
while(path.top() != x)
{
temp.push(path.top());
path.pop();
}
int t = x;
pair<int, int> tt = {c, x};
vonalak[tt] = vonalak[tt]+1;
maxc = max(maxc, vonalak[tt]);
while(!temp.empty())
{
tt = {t, temp.top()};
vonalak[tt] = vonalak[tt]+1;
maxc = max(maxc, vonalak[tt]);
t = temp.top();
path.push(temp.top());
temp.pop();
}
jo = true;
continue;
}
bejar(graf, n, x);
}
szin[c] = 0;
path.pop();
}
int main()
{
GOTTAGOFAST
int n, k;
cin >> n >> k;
szin.resize(n+1);
fill(szin.begin(), szin.end(), 0);
vector<vector<int>> graf(n+1);
int a, b;
for (size_t i = 0; i < k; i++)
{
cin >> a >> b;
graf[a].push_back(b);
}
for (size_t i = 1; i <= n; i++)
{
if(szin[i] > 0) continue;
bejar(graf, n, i);
if(jo) break;
}
auto it = vonalak.begin();
stack<pair<int, int>> megoldasok;
while(it != vonalak.end())
{
if(it->second == maxc)
megoldasok.push(it->first);
++it;
}
cout << megoldasok.size() << "\n";
while(!megoldasok.empty())
{
cout << megoldasok.top().first << " " << megoldasok.top().second << "\n";
megoldasok.pop();
}
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 4/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1892 KiB | |||
2 | Időlimit túllépés | 0/0 | 400ms | 4064 KiB | |||
3 | Elfogadva | 1/1 | 3ms | 2328 KiB | |||
4 | Elfogadva | 1/1 | 3ms | 2676 KiB | |||
5 | Időlimit túllépés | 0/1 | 361ms | 2716 KiB | |||
6 | Időlimit túllépés | 0/1 | 375ms | 2152 KiB | |||
7 | Időlimit túllépés | 0/1 | 372ms | 2420 KiB | |||
8 | Időlimit túllépés | 0/2 | 363ms | 2728 KiB | |||
9 | Időlimit túllépés | 0/2 | 379ms | 2968 KiB | |||
10 | Elfogadva | 2/2 | 202ms | 3732 KiB | |||
11 | Időlimit túllépés | 0/2 | 361ms | 3188 KiB | |||
12 | Időlimit túllépés | 0/2 | 338ms | 2628 KiB | |||
13 | Időlimit túllépés | 0/2 | 367ms | 3888 KiB | |||
14 | Időlimit túllépés | 0/2 | 384ms | 3772 KiB | |||
15 | Időlimit túllépés | 0/2 | 375ms | 4580 KiB | |||
16 | Időlimit túllépés | 0/2 | 367ms | 4232 KiB | |||
17 | Időlimit túllépés | 0/2 | 379ms | 4812 KiB | |||
18 | Időlimit túllépés | 0/2 | 365ms | 5644 KiB | |||
19 | Időlimit túllépés | 0/2 | 368ms | 5484 KiB | |||
20 | Időlimit túllépés | 0/2 | 379ms | 5688 KiB | |||
21 | Időlimit túllépés | 0/2 | 363ms | 6088 KiB | |||
22 | Időlimit túllépés | 0/2 | 375ms | 5920 KiB | |||
23 | Időlimit túllépés | 0/3 | 400ms | 5924 KiB | |||
24 | Időlimit túllépés | 0/4 | 361ms | 5780 KiB | |||
25 | Időlimit túllépés | 0/4 | 344ms | 5864 KiB | |||
26 | Időlimit túllépés | 0/4 | 340ms | 6520 KiB |