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 haveCycle;
  113.     int color[N];
  114.  
  115.     void checkCycle(int u) {
  116.         if (haveCycle) return;
  117.         color[u] = 1;
  118.         for(ii e : G[u]) {
  119.             int v = e.fi;
  120.             if (color[v] == 1) {
  121.                 haveCycle = true;
  122.                 return;
  123.             }
  124.             if (!color[v])
  125.                 checkCycle(v);
  126.         }
  127.         color[u] = 2;
  128.     }
  129.  
  130.     int dist[N];
  131.     int revDFS(int u) {
  132.         if (dist[u] != -1) return dist[u];
  133.         dist[u] = 0;
  134.         for(int v : revG[u]) maximize(dist[u], revDFS(v) + 1);
  135.         return dist[u];
  136.     }
  137.  
  138.     void solve() {
  139.         FOR(i, 1, numNode) color[i] = 0;
  140.         haveCycle = false;
  141.         FOR(i, 1, numNode) if (!color[i]) {
  142.             checkCycle(i);
  143.         }
  144.  
  145.         if (haveCycle) {
  146.             cout << "-1\n";
  147.             return;
  148.         }
  149.  
  150.         FOR(i, 1, numNode) dist[i] = -1;
  151.         int ans = 0;
  152.         FOR(i, 1, numNode) maximize(ans, revDFS(i));
  153.         cout << ans << '\n';
  154.     }
  155. }
  156.  
  157. namespace Subtask5 {
  158.     bool check() {
  159.         return numDir == 0;
  160.     }
  161.  
  162.     int lab[N];
  163.     int root(int v) {
  164.         return (lab[v] < 0 ? v : lab[v] = root(lab[v]));
  165.     }
  166.  
  167.     bool unite(int u, int v) {
  168.         u = root(u); v = root(v);
  169.         if (u == v) return false;
  170.         if (lab[u] > lab[v]) swap(u, v);
  171.         lab[u] += lab[v];
  172.         lab[v] = u;
  173.         return true;
  174.     }
  175.  
  176.     bool vis[N];
  177.     int top, diameter;
  178.     void dfs(int u, int par, int dist = 0) {
  179.         if (dist > diameter) diameter = dist, top = u;
  180.         vis[u] = true;
  181.         for(ii e : G[u]) {
  182.             int v = e.fi;
  183.             if (v == par) continue;
  184.             dfs(v, u, dist + 1);
  185.         }
  186.     }
  187.  
  188.     void solve() {
  189.         FOR(i, 1, numNode) lab[i] = -1;
  190.         bool haveCycle = false;
  191.         FOR(i, 1, numUndir)
  192.             if (!unite(edge[i].fi, edge[i].se)) haveCycle = true;
  193.  
  194.         if (haveCycle) {
  195.             cout << "-1\n";
  196.             return;
  197.         }
  198.  
  199.         FOR(i, 1, numNode) vis[i] = false;
  200.         int ans = 0;
  201.         FOR(i, 1, numNode) if (!vis[i]) {
  202.             diameter = 0;
  203.             dfs(1, -1);
  204.             dfs(top, -1);
  205.             maximize(ans, diameter);
  206.         }
  207.         cout << ans << '\n';
  208.     }
  209. }
  210.  
  211. void process() {
  212.     if (Subtask123 :: check()) Subtask123 :: solve();
  213.     else if (Subtask4 :: check()) Subtask4 :: solve();
  214.     else if (Subtask5 :: check()) Subtask5 :: solve();
  215. }
  216.  
  217. int main() {
  218.     ios_base::sync_with_stdio(0);
  219.     cin.tie(0); cout.tie(0);
  220.     if (fopen(task".inp", "r")) {
  221.         freopen(task".inp", "r", stdin);
  222.         freopen(task".out", "w", stdout);
  223.     }
  224.     int tc = 1;
  225.     cin >> tc;
  226.     while(tc--) {
  227.         init();
  228.         process();
  229.     }
  230.     return 0;
  231. }
  232.  
Success #stdin #stdout 0.01s 20024KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/7ZjyjI
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!