| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 109938 |
2019-05-08T12:10:36 Z |
MetB |
Islands (IOI08_islands) |
C++17 |
|
766 ms |
132096 KB |
#include <iostream>
#include <cstdlib>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <bitset>
#include <queue>
#include <math.h>
#include <stack>
#include <vector>
#include <string.h>
#include <random>
typedef long long ll;
const ll MOD = 1e9 + 7, INF = 1e18;
using namespace std;
int n, m, p[1000001], cost[1000001];
bitset <1000000> is_cycle, u, c;
ll d[1000001][2];
ll pref[2000001];
deque < pair <ll, int> > q_max;
vector < pair <int, int> > g_un[1000001], g_t[1000001];
vector < pair <int, int> > cycle[1000001];
void dfs_traverse (ll x)
{
c[x] = 1;
for (auto to : g_t[x])
if (!c[to.first])
dfs_traverse (to.first);
for (auto to : g_un[x])
if (!c[to.first])
dfs_traverse (to.first);
}
bool dfs_cycle (ll x, ll par, ll color)
{
u[x] = 1;
for (auto to : g_t[x])
{
if (u[to.first] == 1)
{
ll v = x;
while (v != to.first)
{
cycle[color].emplace_back (v, cost[v]);
is_cycle[v] = true;
v = p[v];
}
cycle[color].emplace_back (to.first, to.second);
is_cycle[to.first] = true;
return true;
}
else if (!u[to.first])
{
p[to.first] = x;
cost[to.first] = to.second;
if (dfs_cycle (to.first, x, color)) return true;
}
}
u[x] = 2;
return false;
}
ll find_diameter (ll x, ll p)
{
ll sum = 0, mx = 0, smx = 0;
for (auto to : g_un[x])
if (to.first != p && !is_cycle[to.first])
{
sum = max (sum, find_diameter (to.first, x));
if (mx <= d[to.first][0] + to.second)
{
smx = mx;
mx = d[to.first][0] + to.second;
}
else smx = max (smx, d[to.first][0] + to.second);
}
d[x][0] = mx;
d[x][1] = smx;
return max (sum, mx + smx);
}
ll process (vector < pair <int, int> > & cycle)
{
ll diameter = 0;
for (auto x : cycle)
diameter = max (diameter, find_diameter (x.first, -1));
ll s = cycle.size ();
for (ll i = 2 * cycle.size () - 1; i >= 0; i--)
pref[i] = cycle[i % s].second + (i != 2 * cycle.size () - 1 ? pref[i+1] : 0);
q_max.clear ();
for (ll i = 0; i < s - 1; i++)
{
while (!q_max.empty () && q_max.back ().first <= pref[i] + d[cycle[i % s].first][0])
q_max.pop_back ();
q_max.emplace_back (pref[i] + d[cycle[i % s].first][0], i);
}
for (ll i = s - 1; i < 2 * cycle.size (); i++)
{
ll k = q_max.front ().first;
diameter = max (diameter, k - pref[i] + d[cycle[i % s].first][0]);
while (!q_max.empty () && q_max.back ().first <= pref[i] + d[cycle[i % s].first][0])
q_max.pop_back ();
q_max.emplace_back (pref[i] + d[cycle[i % s].first][0], i);
while (!q_max.empty () && q_max.front ().second <= i - s + 1)
q_max.pop_front ();
}
return diameter;
}
int main ()
{
cin >> n;
for (ll i = 0; i < n; i++)
{
ll x, l;
scanf ("%lld%lld", &x, &l);
g_t[i].emplace_back (x - 1, l);
g_un[x - 1].emplace_back (i, l);
}
ll color = 0;
for (ll i = 0; i < n; i++)
if (!u[i] && !c[i])
{
dfs_cycle (i, -1, ++color);
dfs_traverse (i);
}
ll ans = 0;
for (ll i = 1; i <= color; i++)
ans += process (cycle[i]);
cout << ans;
}
Compilation message
islands.cpp: In function 'll process(std::vector<std::pair<int, int> >&)':
islands.cpp:109:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
pref[i] = cycle[i % s].second + (i != 2 * cycle.size () - 1 ? pref[i+1] : 0);
~~^~~~~~~~~~~~~~~~~~~~~~~~
islands.cpp:121:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (ll i = s - 1; i < 2 * cycle.size (); i++)
~~^~~~~~~~~~~~~~~~~~~
islands.cpp: In function 'int main()':
islands.cpp:146:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%lld%lld", &x, &l);
~~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
70748 KB |
Output is correct |
| 2 |
Correct |
84 ms |
70776 KB |
Output is correct |
| 3 |
Correct |
69 ms |
70904 KB |
Output is correct |
| 4 |
Correct |
79 ms |
70844 KB |
Output is correct |
| 5 |
Correct |
72 ms |
70776 KB |
Output is correct |
| 6 |
Correct |
70 ms |
70904 KB |
Output is correct |
| 7 |
Correct |
76 ms |
70776 KB |
Output is correct |
| 8 |
Correct |
73 ms |
70800 KB |
Output is correct |
| 9 |
Correct |
71 ms |
70848 KB |
Output is correct |
| 10 |
Correct |
70 ms |
70776 KB |
Output is correct |
| 11 |
Correct |
69 ms |
70776 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
74 ms |
70996 KB |
Output is correct |
| 2 |
Correct |
70 ms |
71004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
72 ms |
70904 KB |
Output is correct |
| 2 |
Correct |
77 ms |
71368 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
72380 KB |
Output is correct |
| 2 |
Correct |
114 ms |
75692 KB |
Output is correct |
| 3 |
Correct |
95 ms |
72484 KB |
Output is correct |
| 4 |
Correct |
82 ms |
71644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
120 ms |
77560 KB |
Output is correct |
| 2 |
Correct |
129 ms |
81756 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
218 ms |
88820 KB |
Output is correct |
| 2 |
Correct |
286 ms |
102688 KB |
Output is correct |
| 3 |
Correct |
260 ms |
114152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
323 ms |
105844 KB |
Output is correct |
| 2 |
Runtime error |
366 ms |
132096 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
456 ms |
128812 KB |
Output is correct |
| 2 |
Runtime error |
766 ms |
132096 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
467 ms |
132096 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
