Submission #373321
Source Code Expand
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;
struct add_segtree
{
static const int DEPTH = 18;
static const int SIZE = 1 << DEPTH;
int cnt[2 * SIZE];
void init()
{
for (int i = 0; i < 2 * SIZE; ++i) {
cnt[i] = 0;
}
}
void add(int p, int v)
{
p += SIZE;
cnt[p] += v;
p >>= 1;
while (p) {
cnt[p] = cnt[p * 2] + cnt[p * 2 + 1];
p >>= 1;
}
}
int query(int L, int R)
{
int r2 = 0;
L += SIZE; R += SIZE;
while (L < R) {
if (L & 1) {
r2 += cnt[L];
L++;
}
if (R & 1) {
--R;
r2 += cnt[R];
}
L >>= 1; R >>= 1;
}
return r2;
}
};
struct max_segtree
{
static const int DEPTH = 18;
static const int SIZE = 1 << DEPTH;
pair<int, int> cnt[2 * SIZE];
void init()
{
for (int i = 0; i < 2 * SIZE; ++i) {
cnt[i] = make_pair(-1, -1);
}
}
void update(int p, int depth, int qL, int qR, pair<int, int> qv)
{
int pL = (p << depth) - SIZE;
int pR = ((p + 1) << depth) - SIZE;
if (pR <= qL || qR <= pL) return;
if (qL <= pL && pR <= qR) {
cnt[p] = max(cnt[p], qv);
return;
}
update(p * 2, depth - 1, qL, qR, qv);
update(p * 2 + 1, depth - 1, qL, qR, qv);
}
void update(int L, int R, pair<int, int> V)
{
update(1, DEPTH, L, R, V);
}
int query(int p)
{
pair<int, int> ret = make_pair(-1, -1);
p += SIZE;
while (p) {
ret = max(ret, cnt[p]);
p >>= 1;
}
return ret.second;
}
};
struct enode
{
int prev, next;
int id, dest;
};
int N, Q, A[100100], B[100100], C[100100];
enode es[300300];
set<pair<int, int> > *edges[100100];
vector<pair<int, int> > graph[100100];
int status[100100]; //0: available, 1: already cut
int be[100100]; //base edge
int eid[100100], eilast; //euler tour id
int vleft[100100], vright[100100], vilast;
int left[100100], right[100100], root[100100];
add_segtree seg1; // edge count manager
max_segtree seg2;
void dfs(int p, int r)
{
vleft[p] = vilast++;
left[p] = eilast;
root[p] = r;
for (auto e : graph[p]) if (e.first != r) {
be[e.first] = e.second;
eid[e.second] = eilast++;
dfs(e.first, p);
}
vright[p] = vilast;
right[p] = eilast;
}
int count_edges(int p)
{
return seg1.query(left[p], right[p]);
}
void cut_edge(int p)
{
// p: real vertex id (cut p -- p.root)
if (p == 0) return;
int w = count_edges(p) + 1;
int ul = seg2.query(vleft[root[p]]);
if (be[ul] != -1) {
seg1.add(eid[be[ul]], w);
}
seg1.add(eid[be[p]], -w);
seg2.update(vleft[p], vright[p], make_pair(left[p], p));
status[be[p]] = 1;
}
int nMove = 0;
void rob(int p, int rt, set<pair<int, int> > *src, set<pair<int, int> > *dest)
{
for (int ep = es[p].next; ep != -1; ep = es[ep].next) {
int dt = es[ep].dest;
int eid = es[ep].id;
if (dt != rt && status[eid] == 0) {
rob(dt, p, src, dest);
++nMove;
src->erase(make_pair(C[eid], eid));
dest->insert(make_pair(C[eid], eid));
}
}
}
void add_edge(int s, int d, int id, int t)
{
if (es[s].next != -1) {
es[es[s].next].prev = t;
es[t].next = es[s].next;
} else {
es[t].next = -1;
}
es[s].next = t;
es[t].prev = s;
es[t].id = id;
es[t].dest = d;
}
void remove_edge(int t)
{
if (es[t].next != -1) es[es[t].next].prev = es[t].prev;
es[es[t].prev].next = es[t].next;
}
int main()
{
scanf("%d", &N);
for (int i = 0; i < N; ++i) edges[i] = new set < pair<int, int> >();
for (int i = 0; i < N; ++i) {
es[i].prev = es[i].next = -1;
es[i].id = es[i].dest = -1;
}
for (int i = 0; i < N - 1; ++i) {
scanf("%d%d%d", A + i, B + i, C + i);
status[i] = 0;
--A[i];
--B[i];
graph[A[i]].push_back(make_pair(B[i], i));
graph[B[i]].push_back(make_pair(A[i], i));
add_edge(A[i], B[i], i, N + 2 * i);
add_edge(B[i], A[i], i, N + 2 * i + 1);
edges[0]->insert(make_pair(C[i], i));
}
be[0] = -1; eilast = 0; vilast = 0;
dfs(0, -1);
seg1.init();
for (int i = 0; i < eilast; ++i) seg1.add(i, 1);
seg2.init();
seg2.update(0, N, make_pair(left[0], 0));
scanf("%d", &Q);
for (; Q--; ) {
int q;
scanf("%d", &q);
if (q == 1) {
int e, d;
scanf("%d%d", &e, &d); --e;
if (status[e] == 1) continue;
//fprintf(stderr, "q1\n");
int eloc = seg2.query(vleft[A[e]]);
if (edges[eloc]->count(make_pair(C[e], e)) == 0) {
fprintf(stderr, "><><\n");
}
edges[eloc]->erase(make_pair(C[e], e));
C[e] += d;
edges[eloc]->insert(make_pair(C[e], e));
} else {
int e;
scanf("%d", &e); --e;
if (status[e] == 1) {
puts("-1");
continue;
}
//fprintf(stderr, "q2\n");
int uroot = seg2.query(vleft[A[e]]);
//printf("u %d\n", uroot);
//fprintf(stderr, "q2 1 %d\n", uroot);
auto beg = edges[uroot]->begin();
if (edges[uroot]->size() == 0) {
fprintf(stderr, "><\n");
}
//fprintf(stderr, "q2 2 %d\n", beg->second);
printf("%d\n", beg->second + 1);
e = beg->second;
int bot = B[e];
if (root[bot] != A[e]) bot = A[e];
//printf("bot %d\n", bot);
//fprintf(stderr, "q2 3 %d %d\n", beg->second, uroot);
edges[uroot]->erase(beg);
//fprintf(stderr, "q2 4 %d\n", beg->second);
cut_edge(bot);
remove_edge(N + 2 * e);
remove_edge(N + 2 * e + 1);
//fprintf(stderr, "q2 5 %d\n", beg->second);
//fprintf(stderr, "%d %d %d\n", count_edges(uroot), count_edges(bot), bot);
if (count_edges(uroot) < count_edges(bot)) {
swap(edges[uroot], edges[bot]);
rob(uroot, root[uroot], edges[bot], edges[uroot]);
} else {
rob(bot, root[bot], edges[uroot], edges[bot]);
}
}
//fprintf(stderr, "end\n");
}
//fprintf(stderr, "%d\n", nMove);
return 0;
}
Submission Info
Submission Time
2015-03-29 16:48:02+0900
Task
I - 盆栽
User
semiexp
Language
C++11 (GCC 4.9.2)
Score
300
Code Size
6091 Byte
Status
AC
Exec Time
623 ms
Memory
33812 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:205:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
^
./Main.cpp:213:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", A + i, B + i, C + i);
^
./Main.cpp:235:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &Q);
^
./Main.cpp:238:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
^
./Main.cpp:242:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &e, &d); --e;
...
Judge Result
Set Name
Subtask
All
Score / Max Score
30 / 30
270 / 270
Status
Set Name
Test Cases
Subtask
atetubou-challenge1.in, subtask_00.txt, subtask_01.txt, subtask_02.txt, subtask_03.txt, subtask_04.txt, subtask_05.txt, subtask_06.txt, subtask_07.txt, subtask_08.txt, subtask_09.txt, subtask_10.txt, subtask_11.txt, subtask_12.txt, subtask_13.txt, subtask_14.txt, subtask_15.txt, subtask_16.txt
All
scrambled_00.txt, scrambled_01.txt, scrambled_02.txt, scrambled_03.txt, scrambled_04.txt, scrambled_05.txt, scrambled_06.txt, scrambled_07.txt, scrambled_08.txt, scrambled_09.txt, scrambled_10.txt, scrambled_11.txt, scrambled_12.txt, scrambled_13.txt, scrambled_14.txt, scrambled_15.txt, scrambled_16.txt, scrambled_17.txt, scrambled_18.txt, scrambled_19.txt, scrambled_20.txt, scrambled_21.txt, scrambled_22.txt, scrambled_23.txt, scrambled_24.txt, scrambled_25.txt, scrambled_26.txt, scrambled_27.txt, scrambled_28.txt, scrambled_29.txt, scrambled_30.txt, scrambled_31.txt, scrambled_32.txt, subtask_00.txt, subtask_01.txt, subtask_02.txt, subtask_03.txt, subtask_04.txt, subtask_05.txt, subtask_06.txt, subtask_07.txt, subtask_08.txt, subtask_09.txt, subtask_10.txt, subtask_11.txt, subtask_12.txt, subtask_13.txt, subtask_14.txt, subtask_15.txt, subtask_16.txt
Case Name
Status
Exec Time
Memory
scrambled_00.txt
AC
47 ms
9244 KB
scrambled_01.txt
AC
45 ms
9516 KB
scrambled_02.txt
AC
45 ms
9504 KB
scrambled_03.txt
AC
45 ms
9500 KB
scrambled_04.txt
AC
45 ms
9504 KB
scrambled_05.txt
AC
45 ms
9504 KB
scrambled_06.txt
AC
44 ms
9508 KB
scrambled_07.txt
AC
45 ms
9508 KB
scrambled_08.txt
AC
45 ms
9512 KB
scrambled_09.txt
AC
45 ms
9508 KB
scrambled_10.txt
AC
46 ms
9572 KB
scrambled_11.txt
AC
549 ms
33688 KB
scrambled_12.txt
AC
558 ms
33692 KB
scrambled_13.txt
AC
560 ms
33696 KB
scrambled_14.txt
AC
559 ms
33696 KB
scrambled_15.txt
AC
613 ms
33692 KB
scrambled_16.txt
AC
576 ms
33696 KB
scrambled_17.txt
AC
559 ms
33700 KB
scrambled_18.txt
AC
604 ms
33696 KB
scrambled_19.txt
AC
581 ms
33632 KB
scrambled_20.txt
AC
598 ms
33692 KB
scrambled_21.txt
AC
295 ms
33812 KB
scrambled_22.txt
AC
52 ms
9584 KB
scrambled_23.txt
AC
46 ms
9572 KB
scrambled_24.txt
AC
58 ms
9516 KB
scrambled_25.txt
AC
52 ms
9500 KB
scrambled_26.txt
AC
46 ms
9520 KB
scrambled_27.txt
AC
623 ms
33700 KB
scrambled_28.txt
AC
613 ms
33692 KB
scrambled_29.txt
AC
603 ms
33624 KB
scrambled_30.txt
AC
605 ms
33692 KB
scrambled_31.txt
AC
584 ms
33696 KB
scrambled_32.txt
AC
45 ms
9240 KB
subtask_00.txt
AC
44 ms
9244 KB
subtask_01.txt
AC
45 ms
9504 KB
subtask_02.txt
AC
46 ms
9512 KB
subtask_03.txt
AC
46 ms
9496 KB
subtask_04.txt
AC
47 ms
9496 KB
subtask_05.txt
AC
46 ms
9568 KB
subtask_06.txt
AC
45 ms
9508 KB
subtask_07.txt
AC
46 ms
9504 KB
subtask_08.txt
AC
46 ms
9556 KB
subtask_09.txt
AC
46 ms
9508 KB
subtask_10.txt
AC
45 ms
9512 KB
subtask_11.txt
AC
45 ms
9500 KB
subtask_12.txt
AC
45 ms
9504 KB
subtask_13.txt
AC
46 ms
9508 KB
subtask_14.txt
AC
46 ms
9584 KB
subtask_15.txt
AC
45 ms
9512 KB
subtask_16.txt
AC
43 ms
9252 KB