A. Radio Prize

All boring tree-shaped lands are alike, while all exciting tree-shaped lands are exciting in their own special ways.What makes Treeland more exciting than the other tree-shaped lands are the raddest radio hosts in the local area: Rootand Leaf. Every morning on FM 32:33 (repeating of course), Root and Leaf of The Full Depth Morning Show serveup the hottest celebrity gossip and traffic updates.

The region of Treeland is made of nn cities, connected by n - 1n−1 roads such that between every pair of cities there isexactly one simple path. The iith road connects cities u_iui​ and v_ivi​, and has a toll of w_iwi​.

To reward their loyal listeners, The Full Depth Morning Show is giving away a number of travel packages! Root andLeaf will choose n - 1n−1 lucky residents from the city that sends them the most fan mail. Each of those residents thengets a distinct ticket to a different city in Treeland.

Each city in Treeland has its own tax on prizes: t_iti​. Let d_{u,v}du,v​be the sum of the tolls on each road on the only simplepath from city uu to vv. For a trip from city uu to city vv, the cost of that trip is then (t_u + t_v)d_{u,v}(tu​+tv​)du,v​.

The shock jocks haven’t quite thought through how much their prize is worth. They need to prepare a report to theradio executives, to summarize the expected costs. For each city that could win the prize, what is the total cost ofpurchasing all the tickets?

The first line of input is a single integer n (1 \leq≤ n \leq≤ 100 000). The next line has nnspace-separated integers t_iti​(1 \leq t_i \leq 1 0001≤ti​≤1000), the tax in each city. The following n - 1n−1 lines each have 3 integers, u_i,v_i,w_iui​,vi​,wi​, meaning the iith roadconnects cities u_iui​ and v_ivi​(1 \leq u_i,v_i \leq n1≤ui​,vi​≤n), with a toll of w_iwi​ (1 \leq w_i \leq 1 0001≤wi​≤1000).

Output nn lines. On the iith line, output a single integer: the cost of purchasing tickets if city i wins the contest

样例输入

5

2 5 3 4 1 1 2 2 2 4 5 4 3 3 5 2 6

样例输出

1

130
159
191
163
171

样例输入2复制

6
4 3 3 4 3 3
1 3 2
2 1 1
1 4 6
4 5 6
6 4 2

样例输出2复制

209
206
232
209
336
232

#include
#include
#include
#include
#include

using namespace std;

using ll = long long;
using pii = pair;

constexpr int MAXN = 100000;
int n;
int t[MAXN];
vector tree[MAXN];

int depth[MAXN];
int sz[MAXN];
ll tsum[MAXN];
ll ans[MAXN];

void dfs1(int u, int p) {
sz[u] = 1;
tsum[u] = t[u];
for (auto& e : tree[u]) {
int v, w;
tie(v, w) = e;

    if (v == p) continue;

    depth\[v\] = depth\[u\] + w;

    dfs1(v, u);

    sz\[u\] += sz\[v\];  
    tsum\[u\] += tsum\[v\];  
}  

}

void dfs2(int u, int p, ll depth_sum, ll tax_depth_sum) {
ans[u] = t[u] * depth_sum + tax_depth_sum;
for (auto& e : tree[u]) {
int v, w;
tie(v, w) = e;
if (v == p) continue;

    dfs2(  
        v,  
        u,  
        depth\_sum + w \* (n - 2 \* sz\[v\]),  
        tax\_depth\_sum + w \* (tsum\[0\] - 2 \* tsum\[v\])  
    );  
}  

}

int main() {
cin >> n;

for (int i = 0; i < n; ++i) {  
    cin >> t\[i\];  
}

for (int i = 1; i < n; ++i) {  
    int u, v, w;  
    cin >> u >> v >> w;  
    --u; --v;  
    tree\[u\].emplace\_back(v, w);  
    tree\[v\].emplace\_back(u, w);  
}

dfs1(0, -1);  
ll depth\_sum = 0;  
ll tax\_depth\_sum = 0;  
for (int i = 0; i < n; ++i) {  
    depth\_sum += depth\[i\];  
    tax\_depth\_sum += 1LL \* t\[i\] \* depth\[i\];  
}

dfs2(0, -1, depth\_sum, tax\_depth\_sum);

for (int i = 0; i < n; ++i) {  
    cout << ans\[i\] << '\\n';  
}

return 0;  

}

B. Perfect Flush

You are given a list of integers x_1,x_2,\ldots,x_nx1​,x2​,…,xn​ and a number kk. It is guaranteed that each i from 1 to k appears in thelist at least once.Find the lexicographically smallest subsequence of x that contains each integer from 1 to k exactly once.

input

The first line will contain two integers nn and kk, with 1 \leq k \leq n \leq 200 0001≤k≤n≤200000. The following n lines will each containan integer x_ixi​ with 1 \leq x_i \leq k1≤xi​≤k.

output

Write out on one line, separated by spaces, the lexicographically smallest subsequence of x that has each integer from 1 to k exactly once

样例输入1复制

6 3
3
2
1
3
1
3

样例输出1复制

2 1 3

样例输入2复制

10 5
5
4
3
2
1
4
1
1
5
5

样例输出2复制

3 2 1 4 5

#include
#include

C. Coloring Contention

Alice and Bob are playing a game on a simple connected graph with N nodes and M edges.Alice colors each edge in the graph red or blue.A path is a sequence of edges where each pair of consecutive edges have a node in common. If the first edge in thepair is of a different color than the second edge, then that is a “color change.”After Alice colors the graph, Bob chooses a path that begins at node 1 and ends at node N. He can choose any path onthe graph, but he wants to minimize the number of color changes in the path. Alice wants to choose an edge coloringto maximize the number of color changes Bob must make. What is the maximum number of color changes she canforce Bob to make, regardless of which path he chooses?

Input

The first line contains two integer values N and M with 2 \leq N \leq 100 0002≤N≤100000 and 1 \leq M \leq 100 0001≤M≤100000. The next M linescontain two integers a_iai​ and b_ibi​ indicating an undirected edge between nodes a_iai​ and b_ibi​ (1 \leq a_i,b_i \leq N1≤ai​,bi​≤N, a_i \neq b_iai​​=bi​).All edges in the graph are unique.

Output

Output the maximum number of color changes Alice can force Bob to make on his route from node 1 to node N

样例输入1复制

3 3
1 3
1 2
2 3

样例输出1复制

0

样例输入2复制

7 8
1 2
1 3
2 4
3 4
4 5
4 6
5 7
6 7

样例输出2复制

3

// #include // this is not C++; this is a Linuxism
#include
#include
#include

using namespace std;

#define all(x) begin(x), end(x)

using ll = long long;
using ld = long double;
using pii = pair;
using vi = vector;

int main() {
int n, m;
cin >> n >> m;
vector graph(n);
for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v;
--u; --v;

    graph\[u\].push\_back(v);  
    graph\[v\].push\_back(u);  
}

vi dist(n, n + 1);  
dist\[0\] = 0;  
queue<int> q;  
q.push(0);  
while (!q.empty()) {  
    int u = q.front();  
    q.pop();  
    for (int v : graph\[u\]) {  
        if (dist\[v\] == n + 1) {  
            dist\[v\] = dist\[u\] + 1;  
            q.push(v);  
        }  
    }  
}

cout << dist.back() - 1 << '\\n';

return 0;  

}

D. Dividing by Two

You are given two integers, A and B. You want to transform A to B by performing a sequence of operations. You canonly perform the following operations:

• Divide A by two, but only if A is even
• Add one to A.

What is the minimum number of operations you need to transform A into B?

input

The input will be a single line containing two integers A and B with 1 \leq A,B \leq 10^91≤A,B≤109.

output

On a single line write the minimum number of operations required as an integer.

样例输入1复制

103 27

样例输出1复制

4

样例输入2复制

3 8

样例输出2复制

5

#include
using namespace std;
int main()
{
long long n,m,ct;
while(scanf("%lld%lld",&n,&m)!=EOF)
{
ct=0;
if(n==m)cout<<"0"<m)
{
while(n>m)
{
if(n%2==0)
{
n/=2;
ct++;
}
else {
n+=1;
ct++;
}
}
while(n<m) {
n+=1;
ct++;
}
cout<<ct<<endl;
}

    }  
}  

}

E. Rainbow Strings

Define a string to be a rainbow string if every letter in the string is distinct. An empty string is also considered a rainbow string.

Given a string of lowercase letters, compute the number of different subsequences which are rainbow strings. Two subsequences are different if an index is included in one subsequence but not the other, even if the resulting strings areidentical.

In the first example, there are 8 subsequences. The only subsequences that aren't rainbow strings are aaaa and aabaab.The remaining 6 subsequences are rainbow strings.

input

The input will consist of a single line with a single string consisting solely of lowercase letters. The length of the stringis between 1 and 100 000 (inclusive).

output

Write on a single line the number of rainbow sequences, modulo the prime 11092019.

样例输入1复制

aab

样例输出1复制

6

样例输入2复制

icpcprogrammingcontest

样例输出2复制

209952

#include
#include
#include
using namespace std ;
typedef long long ll ;
ll MOD = 11092019 ;
int main() {
string s ;
cin >> s ;
vector cnt(256) ;
for (auto c : s)
cnt[(int)c]++ ;
ll r = 1 ;
for (auto v : cnt)
r = (r * (v + 1)) % MOD ;
cout << r << endl ;
}

F. Carny Magician

Charles and Ada are watching a magician shuffling a deck of thirteen numbered cards, which were originally ordered.The magician spreads the cards out on the table.

Ada exclaims, “Odd; ten of the cards are in their original locations!”

Charles thinks for a moment, and says, “Not only that, but it is the forty-second such ordering!”

Can you figure out the order of the cards? Formally, the magician’s cards can be considered as a permutationp_1, p_2, …, p_np1​,p2​,…,pn​, that contains each number from 1 to nn exactlyexactly once. The number of fixed points is the number ofindices ii such that p_i = ipi​=i.

Given three numbers n, mn,m and kk, find the kkth lexicographically smallest permutation of sizesize nn that has exactly m fixed points.

The input will be a single line containing the three integers n, mn,m, and kk, with 0 ≤ m ≤ n0≤m≤n, 1 ≤ n ≤ 501≤n≤50, and 1 ≤ k ≤ 10^{18}1≤k≤1018.

On a single line, write the permutation as a sequence of nn space-separated integers. If there are fewer than kk permutation satisfying the conditions, then print -1 on a single line.

样例输入1复制

3 1 1

样例输出1复制

1 3 2

样例输入2复制

3 2 1

样例输出2复制

-1

样例输入3复制

5 3 7

样例输出3复制

2 1 3 4 5

G. Glow, Little Pixel, Glow

An LCD panel is composed of a grid of pixels, spaced 11 alu (“arbitrary length unit”) apart both horizontally andvertically. Wires run along each row and each column, intersecting at the pixels. Wires are numbered beginning with 11 and proceeding up to a panel-dependent maximum. The vertical wire numbered 11 lies along the left edge of the panel,and the horizontal wire numbered 11 lies along the bottom edge of the panel.

A pixel will activate, turning dark, when a current is present along both the vertical and horizontal wire passing through that pixel.

For a period of time, we will send pulses of current down selected wires. The current flows down the wires at a speedof one alu per atu (“arbitrary time unit”). The pulses themselves have a length measured in atus. A pixel activates when current is passing through both intersecting wires at the same time. If the leading edge of a pulse on one wirereaches the intersection at the exact same time that the trailing edge of a pulse on the other wire leaves that intersection,the pixel is not activated.

All pulses in vertical wires start from the bottom of the grid. All pulses in horizontal wires start from the left of the grid. At most one pulse will travel along any one wire.

Given the schedule of pulses to be sent through the wires, determine how many pixels will have been activated by the time all pulses have exited the top and right of the grid.

The first line will contain nn, the number of current pulses, with 1 ≤ n ≤ 200 0001≤n≤200000.Following this will be nn lines, each describing a single pulse. Each such line will contain four elements, separated from one another by a single space:

• A single character that is either ‘h’ or ‘v’, indicating the horizontal/vertical direction of the pulse.
• An integer t, 1 ≤ t ≤ 200 0001≤t≤200000, denoting the starting time of the pulse. The starting time is considered to be the moment when the leading edge of a vertical [horizontal] pulse crosses horizontal [vertical] wire #1.
• An integer m, 1 ≤ m ≤ 200 0001≤m≤200000, denoting the length of the pulse.
• An integer aa, 1 ≤ a ≤ 100 0001≤a≤100000, denoting the wire number (horizontal or vertical) along which the pulse willtravel.

Print on a single line the number of pixels that will have activated by the time the last pulse of current has left the grid.

样例输入1复制

4
h 1 4 1
v 2 4 2
h 10 2 2
v 11 2 3

样例输出1复制

2

样例输入2复制

4
h 1 10 1
h 5 10 2
v 1 10 1
v 5 10 3

样例输出2复制

4

样例输入3复制

7
v 1 3 1
v 1 15 2
h 4 5 1
h 5 5 2
h 6 5 3
h 7 5 4
h 8 5 5

样例输出3复制

5

#include
#include
#include
using namespace std ;
typedef long long ll ;
struct traininfo {
int tim, end ;
char typ ;
} ;
bool operator<(const traininfo &a, const traininfo &b) { if (a.tim != b.tim) return a.tim < b.tim ; if (a.end != b.end) return a.end < b.end ; return a.typ < b.typ ; } int main() { int n ; cin >> n ;
vector sortme ;
for (int i=0; i> typ >> t0 >> len >> coor ;
sortme.push_back({t0-coor, 1, typ}) ;
sortme.push_back({t0-coor+len, -1, typ}) ;
}
sort(sortme.begin(), sortme.end()) ;
ll rr = 0 ;
ll hcnt = 0, vcnt = 0 ;
for (auto v : sortme) {
if (v.typ == 'h') {
hcnt += v.end ;
if (v.end > 0) {
rr += vcnt ;
}
} else {
vcnt += v.end ;
if (v.end > 0)
rr += hcnt ;
}
}
cout << rr << endl ;
}

H. Pivoting Point

Consider a set of points PP in the plane such that no 33 points are collinear. We construct a “windmill” as follows:

Choose a point pp in PP and a starting direction such that the line through pp in that direction does not intersect any otherpoints in PP.Draw that line.

Slowly rotate the line clockwise like a windmill about the point pp as its pivot until the line intersects another point p'p′ in PP. Designate that point p'p′ to be the new pivot (call this “promoting” the point p'p′), and then continue the rotation.

Continue this process until the line has rotated a full 360360 degrees, returning to its original direction (it can be shown that the line will also return to its original position after a 360360 degree rotation).

During this process, a given point can be promoted multiple times. Considering all possible starting pivots and orientations, find the maximum number of times that a single point can be promoted during a single 360360 degree rotation of a line.

The first line of the input will be a single integer nn with 2 ≤ n ≤ 20002≤n≤2000. Following this will be nn lines, each with two integers x_ixi​ and y_iyi​ with -10 000 ≤ xi,yi ≤ 10 000−10000≤xi,yi≤10000.

On one line, write an integer with the largest number of times any particular point can be a pivot when an arbitrarystarting line does a full rotation as described above.

样例输入1复制

3
-1 0
1 0
0 2

样例输出1复制

2

样例输入2复制

6
0 0
5 0
0 5
5 5
1 2
4 2

样例输出2复制

3

#include
#include
using namespace std ;
using ll = long long ;
const ll INF = 2'000'000'000'000'000'000LL ;
ll add(ll a, ll b) {
ll c = a + b ;
if (c >= INF)
return INF ;
return c ;
}
ll mul(ll a, ll b) {
if (b > 0 && a > INF / b)
return INF ;
return a * b ;
}
const int MAX = 128 ;
ll c[MAX][MAX], f[MAX], g[MAX][MAX] ;
ll g3(ll n, ll m, ll x) {
return mul(c[x][m], g[n-m][x-m]) ;
}
int main(int argc, char *argv[]) {
f[0] = 1 ;
for (int i=1; i> n >> p >> k ;
vector used(n) ;
ll matchable = n ;
ll thiscnt = 0 ;
k-- ;
if (g3(n, p, n) <= k) cout << -1 ; else for (int pos=0; pospos)) ;
if (thiscnt > k) {
if (pos)
cout << " " ; cout << (dig + 1) ; if (dig > pos)
matchable-- ;
if (dig == pos)
p-- ;
used[dig]++ ;
break ;
} else
k -= thiscnt ;
}
}
cout << endl ;
}

I. Error Correction

You are given WW, a set of NN words that are anagrams of each other. There are no duplicate letters in any word. A setof words S \subseteq WS⊆W is called “swap-free” if there is no way to turn a word x \in Sx∈S into another word y \in Sy∈S by swappingonly a single pair of (not necessarily adjacent) letters in xx. Find the size of the largest swap-free set SS chosen from thegiven set WW.

The first line of input contains an integer NN (1 ≤ N ≤ 5001≤N≤500). Following that are NN lines each with a single word.Every word contains only lowercase English letters and no duplicate letters. All NN words are unique, have at least oneletter, and every word is an anagram of every other word.

Output the size of the largest swap-free set

样例输入1复制

6
abc
acb
cab
cba
bac
bca

样例输出1复制

3

样例输入2复制

11
alerts
alters
artels
estral
laster
ratels
salter
slater
staler
stelar
talers

样例输出2复制

8

样例输入3复制

6
ates
east
eats
etas
sate
teas

样例输出3复制

4

#include
#include
#include

J. Interstellar Travel

You are planning to travel in interstellar space in the hope of finding habitable planets. You have already identified NN stars that can recharge your spaceship via its solar panels. The only work left is to decide the orientation of thespaceship that maximizes the distance it can travel.

Space is modeled as a 2D2D plane, with the Earth at the origin. The spaceship can be launched from the Earth in a straight line, in any direction. Star ii can provide enough energy to travel T_iTi​ distance if the spaceship is launched at an angle of a_iai​ with the xx-axis. If the angle is not perfectly aligned, then the spaceship gets less energy. Specifically, if the launch direction makes an angle of aa with the xx-axis, then it gets enough energy to travel distance of

max(0, T_i-s_i * dist(a_i,a))max(0,Ti​−si​∗dist(ai​,a))

from star ii, where dist(a, b)dist(a,b) is the minimum radians needed to go from angle aa to bb. The distance that the spaceship can travel is simply the sum of the distances that each star contributes. Find the maximum distance TT that the star ship can travel.

The first line contains the value NN, 1 ≤ N ≤ 10^51≤N≤105. Following this are NN lines each containing three real numbers T_iTi​,s_isi​, and a_iai​, with 0 < T_i ≤ 1 0000<Ti​≤1000, 0 ≤ si ≤ 1000≤si≤100, and 0 ≤ a_i < 2\pi0≤ai​<2π. All real numbers in the input have at most 66 digits after the decimal point.

On a single line output the maximum distance the spacecraft can travel. Your answer is considered correct if it has anabsolute or relative error of at most 10^{−6}10−6.

本题答案不唯一，符合要求的答案均正确

样例输入1复制

2
100 1 1
100 1 1.5

样例输出1复制

199.500000

样例输入2复制

4
100 1 0.5
200 1 1
100 0.5 1.5
10 2 3

样例输出2复制

405.500000

#include
#include
#include
#define _USE_MATH_DEFINES
#include

#define f first
#define s second

using namespace std;

typedef long long ll;
typedef pair di;
typedef vector vdi;
typedef vector vd;
typedef pair dd;
typedef vector

vdd dist\_deriv;  
double cur = 0;  
for (ll i = 0; i < N; ++i) {  
    if (s\[i\] != 0 && T\[i\]/s\[i\] < M\_PI) {  
        dist\_deriv.emplace\_back(a\[i\] - T\[i\]/s\[i\], s\[i\]);  
        dist\_deriv.emplace\_back(a\[i\], -s\[i\]\*2);  
        dist\_deriv.emplace\_back(a\[i\] + T\[i\]/s\[i\], s\[i\]);

        dist\_deriv.emplace\_back(a\[i\] - T\[i\]/s\[i\] + 2\*M\_PI, s\[i\]);  
        dist\_deriv.emplace\_back(a\[i\] + 2\*M\_PI, -s\[i\]\*2);  
        dist\_deriv.emplace\_back(a\[i\] + T\[i\]/s\[i\] + 2\*M\_PI, s\[i\]);  
    } else {  
        cur += T\[i\] - s\[i\]\*M\_PI;  
        dist\_deriv.emplace\_back(a\[i\] - M\_PI, s\[i\]);  
        dist\_deriv.emplace\_back(a\[i\], -s\[i\]\*2);  
        dist\_deriv.emplace\_back(a\[i\] + M\_PI, 2\*s\[i\]);  
        dist\_deriv.emplace\_back(a\[i\] + 2\*M\_PI, -s\[i\]\*2);  
        dist\_deriv.emplace\_back(a\[i\] + 3\*M\_PI, s\[i\]);  
    }  
}

sort(dist\_deriv.begin(), dist\_deriv.end());

double last\_angle = dist\_deriv\[0\].f;  
double best = cur;  
double c\_deriv = 0;

for (ll i = 0; i < dist\_deriv.size(); ++i) {  
    cur += c\_deriv \* (dist\_deriv\[i\].f - last\_angle);  
    c\_deriv += dist\_deriv\[i\].s;  
    last\_angle = dist\_deriv\[i\].f;  
    best = max(best, cur);  
}

printf("%.6lf\\n", best);