| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 98944 |
2019-02-27T16:26:49 Z |
Akashi |
Toll (APIO13_toll) |
C++14 |
|
12 ms |
7936 KB |
#include <bits/stdc++.h>
using namespace std;
struct edge{
int x, y, k, ok;
bool operator < (const edge &aux)const{
if(k != aux.k) return k < aux.k;
return ok > aux.ok;
}
};
int tt[100005], RG[100005];
inline int Find(int x){
int R = x;
while(R != tt[R]) R = tt[R];
while(x != tt[x]){
int aux = tt[x];
tt[x] = R; x = aux;
}
return R;
}
inline void Union(int x, int y){
if(RG[x] > RG[y]) tt[y] = x;
else if(RG[x] < RG[y]) tt[x] = y;
else{
++RG[x];
tt[y] = x;
}
}
edge a[300005];
vector <pair <int, int> > v[100005];
vector <int> lant[100005];
int **Arb, **w;
int nrl, n, m, k;
int TT[100005], TT_lant[100005], wlant[100005], nrp[100005], val[100005], pos[100005], H[100005];
namespace aint{
void build(int i, int st, int dr, int nod){
if(st == dr){
Arb[i][nod] = val[lant[i][st - 1]];
w[i][nod] = st;
return ;
}
int mij = (st + dr) / 2;
build(i, st, mij, nod * 2);
build(i, mij + 1, dr, nod * 2 + 1);
if(Arb[i][nod * 2] >= Arb[i][nod * 2 + 1]){
Arb[i][nod] = Arb[i][nod * 2];
w[i][nod] = w[i][nod * 2];
}
else{
Arb[i][nod] = Arb[i][nod * 2 + 1];
w[i][nod] = w[i][nod * 2 + 1];
}
}
void update(int i, int st, int dr, int nod, int x, int y){
if(st == dr){
Arb[i][nod] = y;
return ;
}
int mij = (st + dr) / 2;
if(x <= mij) update(i, st, mij, nod * 2, x, y);
else update(i, mij + 1, dr, nod * 2 + 1, x, y);
if(Arb[i][nod * 2] >= Arb[i][nod * 2 + 1]){
Arb[i][nod] = Arb[i][nod * 2];
w[i][nod] = w[i][nod * 2];
}
else{
Arb[i][nod] = Arb[i][nod * 2 + 1];
w[i][nod] = w[i][nod * 2 + 1];
}
}
pair <int, int> query(int i, int st, int dr, int nod, int x, int y){
if(x <= st && dr <= y) return {Arb[i][nod], w[i][nod]};
int mij = (st + dr) / 2;
pair <int, int> p1 = {0, 0};
pair <int, int> p2 = {0, 0};
if(x <= mij) p1 = query(i, st, mij, nod * 2, x, y);
if(mij + 1 <= y) p2 = query(i, mij + 1, dr, nod * 2 + 1, x, y);
if(p1.first >= p2.first) return p1;
return p2;
}
}
inline int dfs(int nod = 1){
int w = 0, frunza = 1, sz = 0, max_sz = 0;
for(auto it : v[nod]){
if(it.first == TT[nod]) continue ;
frunza = 0;
H[it.first] = H[nod] + 1;
val[it.first] = it.second;
TT[it.first] = nod;
int c_sz = dfs(it.first);
sz += c_sz;
if(c_sz > max_sz){
w = it.first;
max_sz = c_sz;
}
}
if(frunza){
lant[++nrl].push_back(nod);
wlant[nod] = nrl;
return 1;
}
int wl = wlant[w];
wlant[nod] = wl;
lant[wl].push_back(nod);
for(auto it : v[nod]){
if(it.first == TT[nod]) continue ;
TT_lant[it.first] = wl;
}
return sz + 1;
}
pair <int, int> ans(int x, int y){
pair <int, int> Sol = {0, 0};
while(1){
int lx = wlant[x], ly = wlant[y];
if(lx == ly){
int st = min(pos[x], pos[y]);
int dr = max(pos[x], pos[y]);
if(st < dr)
Sol = max(Sol, aint :: query(lx, 1, lant[lx].size(), 1, st + 1, dr));
break ;
}
if(H[lant[lx][0]] < H[lant[ly][0]]) swap(x, y), swap(lx, ly);
Sol = max(Sol, aint :: query(lx, 1, lant[lx].size(), 1, 1, pos[x]));
x = lant[lx][0];
x = TT[x];
}
return Sol;
}
struct usu{
int x, k, ok;
};
vector <usu> v2[100005];
vector <int> Sol;
vector <int> Sol2;
void dfs2(int nod = 1){
int cnt = 0;
for(auto it : v2[nod]){
if(it.x == TT[nod]) continue ;
TT[it.x] = nod;
dfs2(it.x);
if(it.ok) Sol.push_back(nrp[it.x]);
nrp[nod] += nrp[it.x];
}
}
int main()
{
// freopen("1.in", "r", stdin);
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= m ; ++i)
scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].k);
for(int i = 1; i <= n ; ++i) tt[i] = i, RG[i] = 1;
sort(a + 1, a + m + 1);
for(int i = 1; i <= m ; ++i){
if(Find(a[i].x) != Find(a[i].y)){
Union(Find(a[i].x), Find(a[i].y));
v[a[i].x].push_back({a[i].y, a[i].k});
v[a[i].y].push_back({a[i].x, a[i].k});
}
}
dfs();
Arb = new int*[nrl + 1];
w = new int*[nrl + 1];
for(int i = 1; i <= nrl ; ++i){
reverse(lant[i].begin(), lant[i].end());
Arb[i] = new int[lant[i].size() * 4 + 5];
w[i] = new int[lant[i].size() * 4 + 5];
aint :: build(i, 1, lant[i].size(), 1);
int NR = 0;
for(auto it : lant[i])
pos[it] = ++NR;
}
int x, y;
vector <int> val;
for(int i = 1; i <= k ; ++i){
scanf("%d%d", &x, &y);
pair <int, int> p = ans(x, y);
val.push_back(p.first);
if(p.second == 0) continue ;
aint :: update(wlant[p.second], 1, lant[wlant[p.second]].size(), 1, pos[p.second], 0);
a[++m] = {x, y, p.first, 1};
Sol2.push_back(p.first);
}
for(int i = 1; i <= n ; ++i) tt[i] = i, RG[i] = 1;
sort(a + 1, a + m + 1);
for(int i = 1; i <= m ; ++i){
if(Find(a[i].x) != Find(a[i].y)){
Union(Find(a[i].x), Find(a[i].y));
v2[a[i].x].push_back({a[i].y, a[i].k, a[i].ok});
v2[a[i].y].push_back({a[i].x, a[i].k, a[i].ok});
}
}
for(int i = 1; i <= n ; ++i)
scanf("%d", &nrp[i]);
memset(TT, 0, sizeof(TT));
dfs2();
long long mm = 0;
sort(Sol.begin(), Sol.end());
sort(Sol2.begin(), Sol2.end());
for(int i = 0; i < Sol.size() ; ++i)
mm = 1LL * Sol[i] * Sol2[i];
printf("%lld", mm);
return 0;
}
Compilation message
toll.cpp: In function 'void dfs2(int)':
toll.cpp:166:9: warning: unused variable 'cnt' [-Wunused-variable]
int cnt = 0;
^~~
toll.cpp: In function 'int main()':
toll.cpp:243:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < Sol.size() ; ++i)
~~^~~~~~~~~~~~
toll.cpp:180:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &n, &m, &k);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:183:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].k);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:213:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~
toll.cpp:234:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &nrp[i]);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7808 KB |
Output is correct |
| 2 |
Correct |
9 ms |
7808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7808 KB |
Output is correct |
| 2 |
Correct |
9 ms |
7808 KB |
Output is correct |
| 3 |
Incorrect |
12 ms |
7936 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7808 KB |
Output is correct |
| 2 |
Correct |
9 ms |
7808 KB |
Output is correct |
| 3 |
Incorrect |
12 ms |
7936 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7808 KB |
Output is correct |
| 2 |
Correct |
9 ms |
7808 KB |
Output is correct |
| 3 |
Incorrect |
12 ms |
7936 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7808 KB |
Output is correct |
| 2 |
Correct |
9 ms |
7808 KB |
Output is correct |
| 3 |
Incorrect |
12 ms |
7936 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
