fork download
copy 
  1. // ~icebear love attt~
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. template<class T>
  6.     bool minimize(T &a, const T &b) {
  7.         if (a > b) return a = b, true;
  8.         return false;
  9.     }
  10.  
  11. template<class T>
  12.     bool maximize(T &a, const T &b) {
  13.         if (a < b) return a = b, true;
  14.         return false;
  15.     }
  16.  
  17. typedef long long ll;
  18. typedef pair<int, int> ii;
  19. typedef pair<int, ii> iii;
  20.  
  21. #define FOR(i, a, b) for(int i = (a); i <= (b); i++)
  22. #define FORR(i, a, b) for(int i = (a); i >= (b); i--)
  23. #define REP(i, n) for(int i = 0; i < (n); i++)
  24. #define RED(i, n) for(int i = (n) - 1; i >= 0; i--)
  25. #define all(v) v.begin(), v.end()
  26. #define fi first
  27. #define se second
  28. #define pb push_back
  29. #define mp make_pair
  30. #define MASK(i) (1LL << (i))
  31. #define task "fakerfmvp"
  32.  
  33. const int MOD = 1e9 + 7;
  34. const int inf = 1e9 + 27092008;
  35. const ll INF = 1e18 + 27092008;
  36. const int N = 2e5 + 5;
  37. int numNode, numUndir, numDir;
  38. vector<ii> G[N];
  39. vector<int> revG[N];
  40. int numState;
  41. ii edge[3 * N];
  42.  
  43. void init() {
  44.     cin >> numNode >> numUndir >> numDir;
  45.  
  46.     numState = 2 * numUndir + numDir;
  47.     FOR(i, 1, numNode) {
  48.         G[i].clear();
  49.         revG[i].clear();
  50.     }
  51.  
  52.     FOR(i, 1, numUndir) {
  53.         int u, v;
  54.         cin >> u >> v;
  55.         G[u].pb(mp(v, i + numDir));
  56.         G[v].pb(mp(u, i + numDir));
  57.         edge[i + numDir] = mp(u, v);
  58.         edge[i + numUndir + numDir] = mp(v, u);
  59.     }
  60.     FOR(i, 1, numDir) {
  61.         int u, v;
  62.         cin >> u >> v;
  63.         edge[i] = mp(u, v);
  64.         G[u].pb(mp(v, i));
  65.         revG[v].pb(u);
  66.     }
  67. }
  68.  
  69. namespace Subtask123 {
  70.     bool check() {
  71.         return max({numNode, numDir, numUndir}) <= 1000;
  72.     }
  73.  
  74.     int dist[N], countState[N];
  75.     vector<int> adj[N];
  76.  
  77.     int fordBellman() {
  78.         queue<int> q;
  79.         FOR(i, 1, numState) {
  80.             countState[i] = 0;
  81.             dist[i] = -1;
  82.             q.push(i);
  83.         }
  84.  
  85.         while(!q.empty()) {
  86.             int state = q.front(); q.pop();
  87.             if (++countState[state] > numState) return -1;
  88.             for(int nxt : adj[state])
  89.                 if (minimize(dist[nxt], dist[state] - 1))
  90.                     q.push(nxt);
  91.         }
  92.  
  93.         return -(*min_element(dist + 1, dist + numState + 1));
  94.     }
  95.  
  96.     void solve() {
  97.         FOR(i, 1, numState) adj[i].clear();
  98.         FOR(i, 1, numState) FOR(j, 1, numState) if (edge[i].se == edge[j].fi) {
  99.             if (i > numDir && j > numDir && abs(i - j) == numUndir) continue;
  100.             adj[i].pb(j);
  101.         }
  102.  
  103.         cout << fordBellman() << '\n';
  104.     }
  105. }
  106.  
  107. namespace Subtask4 {
  108.     bool check() {
  109.         return numUndir == 0;
  110.     }
  111.  
  112.     bool vis[N], haveCycle;
  113.     void checkCycle(int u) {
  114.         if (haveCycle) return;
  115.         vis[u] = true;
  116.         for(ii e : G[u]) {
  117.             int v = e.fi;
  118.             if (vis[v]) {
  119.                 haveCycle = true;
  120.                 return;
  121.             }
  122.             checkCycle(v);
  123.         }
  124.     }
  125.  
  126.     int dist[N];
  127.     int revDFS(int u) {
  128.         if (dist[u]) return dist[u];
  129.         for(int v : revG[u])
  130.             dist[u] = max(dist[u], revDFS(v) + 1);
  131.         return dist[u];
  132.     }
  133.  
  134.     void solve() {
  135.         FOR(i, 1, numNode) vis[i] = false;
  136.         haveCycle = false;
  137.         FOR(i, 1, numNode) if (!vis[i]) {
  138.             checkCycle(i);
  139.         }
  140.  
  141.         if (haveCycle) {
  142.             cout << "-1\n";
  143.             return;
  144.         }
  145.  
  146.         FOR(i, 1, numNode) dist[i] = 0;
  147.         int ans = 0;
  148.         FOR(i, 1, numNode) maximize(ans, revDFS(i));
  149.         cout << ans << '\n';
  150.     }
  151. }
  152.  
  153. namespace Subtask5 {
  154.     bool check() {
  155.         return numDir == 0;
  156.     }
  157.  
  158.     int lab[N];
  159.     int root(int v) {
  160.         return (lab[v] < 0 ? v : lab[v] = root(lab[v]));
  161.     }
  162.  
  163.     bool unite(int u, int v) {
  164.         u = root(u); v = root(v);
  165.         if (u == v) return false;
  166.         if (lab[u] > lab[v]) swap(u, v);
  167.         lab[u] += lab[v];
  168.         lab[v] = u;
  169.         return true;
  170.     }
  171.  
  172.     int h[N], rootA, rootB;
  173.     void dfs(int u, int par) {
  174.         if (h[u] > h[rootA]) rootA = u;
  175.         for(ii e : G[u]) {
  176.             int v = e.fi;
  177.             if (v == par) continue;
  178.             h[v] = h[u] + 1;
  179.             dfs(v, u);
  180.         }
  181.     }
  182.  
  183.     void solve() {
  184.         FOR(i, 1, numNode) lab[i] = -1;
  185.         bool haveCycle = false;
  186.         FOR(i, 1, numUndir)
  187.             if (!unite(edge[i].fi, edge[i].se)) haveCycle = true;
  188.  
  189.         if (haveCycle) {
  190.             cout << "-1\n";
  191.             return;
  192.         }
  193.  
  194.         FOR(i, 1, numNode) h[i] = 0;
  195.         int ans = 0;
  196.         FOR(i, 1, numNode) if (!h[i]) {
  197.             h[i] = 1;
  198.             dfs(i, -1);
  199.             rootB = rootA;
  200.             h[rootB] = 1;
  201.             dfs(rootB, -1);
  202.             maximize(ans, h[rootA] - 1);
  203.         }
  204.         cout << ans << '\n';
  205.     }
  206. }
  207.  
  208. void process() {
  209.     if (Subtask123 :: check()) Subtask123 :: solve();
  210.     else if (Subtask4 :: check()) Subtask4 :: solve();
  211.     else if (Subtask5 :: check()) Subtask5 :: solve();
  212. }
  213.  
  214. int main() {
  215.     ios_base::sync_with_stdio(0);
  216.     cin.tie(0); cout.tie(0);
  217.     if (fopen(task".inp", "r")) {
  218.         freopen(task".inp", "r", stdin);
  219.         freopen(task".out", "w", stdout);
  220.     }
  221.     int tc = 1;
  222.     cin >> tc;
  223.     while(tc--) {
  224.         init();
  225.         process();
  226.     }
  227.     return 0;
  228. }
  229.  
Success #stdin #stdout 0.01s 21380KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/a2BNSP
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!