QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#497891	#6438. Crystalfly	Railgun2334	WA	15ms	11824kb	C++20	5.0kb	2024-07-29 20:06:17	2024-07-29 20:06:21

Judging History

你现在查看的是最新测评结果

[2024-07-29 20:06:21]
评测

测评结果：WA
用时：15ms
内存：11824kb

查看

[2024-07-29 20:06:17]
提交

answer

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
#define re read()
#define INF 9223372036854775800
#define fr(i, x, y) for(int i = x, p = y; i <= p; ++i) 
#define rp(i, x, y) for(int i = x, p = y; i >= p; --i)
#define Timeok ((double)clock() / CLOCKS_PER_SEC < MAX_TIME)
const double MAX_TIME = 1.0 - 0.0032;

inline ll read()
{
   ll x = 0, f = 0;
   char ch = getchar();
   while (!isdigit(ch))
      f |= (ch == '-'), ch = getchar();
   while (isdigit(ch))
      x = (x << 1) + (x << 3) + (ch ^= 48), ch = getchar();
   return f ? -x : x;
}

void write(ll x)
{
   if (x < 0)
      putchar('-'), x = -x;
   if (x > 9)
      write(x / 10);
   putchar(x % 10 + 48);
}

inline void W(ll x, char ch)
{
    write(x);
    putchar(ch);
}

/*------------C-O-D-E------------*/

const int N = 5e5 + 4;
ll n, m, T;

struct node
{
    ll nxt, to;
} t[N];

ll a[N], k[N];

ll head[N], tot;
ll f[N], fson[N];


void add(ll u, ll v)
{
    t[++tot].nxt = head[u];
    t[tot].to = v;
    head[u] = tot;
}

void C()
{
    fr(i,1,2*n+3) t[i]={0,0},head[i]=0;
    tot=0;
    fr(i,1,2*n+3) f[i] = 0, fson[i] = 0;
    fr(i,1,n+3) a[i]=0,k[i] =0;
}

void dfs(ll now, ll fa)
{
    for(int i = head[now]; i;i = t[i].nxt)
    {
        ll y = t[i].to;
        if(y == fa) continue;
        dfs(y, now);
    }

    ///////
    ll maxn3 = 0, maxson = 0; 
    for(int i = head[now]; i;i = t[i].nxt)
    {
        ll y = t[i].to;
        if(y == fa) continue;
        if(k[y] == 3)
        {
            maxn3 = max(maxn3, a[y]);
        }
        maxson = max(maxson, a[y]);
    }

    if(maxn3 == 0)
    {
        ll sum = maxson;
        for(int i = head[now]; i; i = t[i].nxt)
        {
            ll y = t[i].to;
            if(y == fa) continue;
            sum += f[y];
        }
        f[now] = sum;
        fson[now] = sum - maxson;

        // W(now, ' '); W(f[now], '\n');
    }
    else
    {
        ll sum = maxson;
        for(int i = head[now]; i; i = t[i].nxt)
        {
            ll y = t[i].to;
            if(y == fa) continue;
            sum += f[y];
        }
        f[now] = sum;
        fson[now] = sum - maxson;

        ////////
        sum = 0;
        for(int i = head[now]; i;i = t[i].nxt)
        {
            ll y = t[i].to;
            if(y == fa) continue;
            sum += f[y];
        }

        bool okmaxn3 = 0;
        ll cha = 0, _a = 0;
        ll sumpre = sum;
        // sum += maxn3;
        for(int i = head[now]; i;i = t[i].nxt)
        {
            sum = sumpre;
            ll y = t[i].to;
            if(y == fa) continue;
            if(k[y] == 3)
            {
                // okmaxn3 = 1;
                sum += a[y];
                for(int j = head[now]; j;j = t[j].nxt)
                {
                    ll v = t[j].to;
                    if(v == fa) continue;
                    if(v == y) continue;
                    ll nownow = a[v] - (f[v] - fson[v]);
                    // if(k[v] == 3) nownow = a[v];
                    if(cha < nownow)
                    {
                        cha = nownow;
                        _a = a[v];
                    }
                }
                sum += cha;
                if(f[now] < sum)
                {
                    f[now] = sum;
                    fson[now] = f[now] - a[y] - _a;
                }
            }
            // else
            // {
            //     // cha = max(cha, a[y] - (f[y] - fson[y]));
            //     // if(a[y] - (f[y] - fson[y]) < 0) continue;
            //     ll nownow = a[y] - (f[y] - fson[y]);
            //     if(k[y] == 3) nownow = a[y];
            //     if(cha < nownow)
            //     {
            //         cha = nownow;
            //         _a = a[y];
            //     }
            //     // W(cha,'\n');
            // }
        }
        // // if(cha == -1) cha = 0;
        // sum += cha;
        //     // puts("233");

        // if(f[now] < sum)
        // {
        //     f[now] = sum;
        //     fson[now] = f[now] - maxn3 - _a;
        // }
    }
}
void solve()
{
    n = re;
    fr(i,1,n) a[i] = re;
    fr(i,1,n) k[i] = re;
    fr(i,1,n-1)
    {
        ll x = re, y = re;
        add(x,y);
        add(y,x);
    }

    dfs(1, 0);
    W(f[1] + a[1], '\n');

    C();
    return;
}
void solve2()
{
	n = re;
    fr(i,1,n) a[i] = re;
    fr(i,1,n) k[i] = re;
	W(n,'\n');
	fr(i,1,n) W(a[i],' ');
	puts("");
	fr(i,1,n) W(k[i],' ');
	puts("");
	fr(i,1,n-1)
    {
        ll x = re, y = re;
		W(x,' ');
		W(y,'\n');
    }
}
void solve3()
{
	n = re;
    fr(i,1,n) a[i] = re;
    fr(i,1,n) k[i] = re;
	fr(i,1,n-1)
    {
        ll x = re, y = re;
    }
	
}
int main()
{
    ll T = re;
	if(T!=100000)
    	for(ll i=1;i<=T;i++)
    	{
    	   	solve();
    	}
	else
	{
		for(ll i=1;i<=T;i++)
    	{
			if(i!=14)
        		solve3();
			else
				solve2();
    	}
	}
    return 0;
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 11824kb

input:

2
5
1 10 100 1000 10000
1 2 1 1 1
1 2
1 3
2 4
2 5
5
1 10 100 1000 10000
1 3 1 1 1
1 2
1 3
2 4
2 5

output:

10101
10111

result:

ok 2 number(s): "10101 10111"

Test #2:

score: 0

Accepted

time: 0ms

memory: 11824kb

input:

10
6
8 1 1 5 8 9
2 1 2 2 2 2
1 2
2 3
2 4
1 5
2 6
6
6 4 4 1 3 6
2 1 3 3 3 3
1 2
1 3
3 4
4 5
5 6
6
10 5 1 8 5 1
1 3 1 2 2 2
1 2
2 3
2 4
2 5
3 6
10
6 8 8 9 6 9 5 6 6 4
2 1 3 3 2 2 2 2 3 1
1 2
1 3
3 4
4 5
5 6
4 7
2 8
7 9
9 10
7
10 9 1 5 7 5 4
1 1 1 2 1 3 2
1 2
1 3
3 4
3 5
5 6
1 7
5
7 1 1 4 2
3 1 3 2 2
1...

output:

result:

ok 10 numbers

Test #3:

score: -100

Wrong Answer

time: 15ms

memory: 7644kb

input:

100000
10
9 1 7 9 5 1 10 5 3 8
2 1 1 3 1 2 2 3 3 1
1 2
2 3
3 4
1 5
2 6
2 7
6 8
7 9
7 10
3
6 6 1
2 1 2
1 2
1 3
10
6 5 3 7 1 5 1 9 7 3
3 1 3 3 1 3 2 2 2 3
1 2
1 3
3 4
4 5
2 6
6 7
4 8
7 9
1 10
7
2 8 9 7 7 9 10
2 3 2 2 3 2 1
1 2
2 3
1 4
3 5
4 6
3 7
1
8
1
1
4
2
7
9 9 9 8 4 2 7
3 1 2 1 1 1 1
1 2
2 3
2 4
3...

output:

7
10 5 2 5 10 5 9 
3 3 3 1 3 1 3 
1 2
1 3
3 4
4 5
1 6
4 7

result:

wrong answer 1st numbers differ - expected: '49', found: '7'