oj.uz

Submission #1068289

# Submission time Handle Problem Language Result Execution time Memory
1068289 2024-08-21T09:06:42 Z TlenekWodoru Truck Driver (IOI23_deliveries) C++17
29 / 100
 5500 ms 20268 KB 
#include<bits/stdc++.h>
#include "deliveries.h"
using namespace std;
struct Edge
{
    int b,c;
};
vector<Edge>D[100009];
int Deliv[100009];
long long NadMna[100009];
long long NadSuma[100009];
long long Suma[100009];
bool CzyGit[100009];
int n;
void DFS(int v, int last)
{
    NadMna[v]=Deliv[v];
    NadSuma[v]=0;
    for(auto[som,o] : D[v])
    {
        if(som==last){continue;}
        DFS(som,v);
        NadMna[v]+=NadMna[som];
        NadSuma[v]+=NadMna[som]*o+NadSuma[som];
    }
}
void DFS2(int v, int last)
{
    long long maxx=0;
    for(auto[som,o] : D[v])
    {
        if(som==last){continue;}
        Suma[som]=Suma[v]+(NadMna[0]-NadMna[som])*o-NadMna[som]*o;
        maxx=max(maxx,NadMna[som]);
        DFS2(som,v);
    }
    maxx=max(maxx,NadMna[0]-NadMna[v]);
    int odj=0;
    if(v==0){odj=1;}
    if(maxx*2>NadMna[0]-odj){CzyGit[v]=0;}
    else{CzyGit[v]=1;}
}
void init(int N, vector<int> AA, vector<int> BB, vector<int> CC, vector<int> W)
{
    n=N;
    for(int i=0;i<n-1;i++)
    {
        int a=AA[i];
        int b=BB[i];
        int c=CC[i];
        D[a].push_back({b,c});
        D[b].push_back({a,c});
    }
    for(int i=0;i<n;i++)
    {
        Deliv[i]=W[i];
    }
    Deliv[0]++;
	return;
}

long long max_time(int v, int x)
{
    if(v==0){x++;}
    Deliv[v]=x;
    DFS(0,-1);
    Suma[0]=NadSuma[0];
    DFS2(0,-1);
    long long wyn=0;
    for(int i=0;i<n;i++)
    {
        if(CzyGit[i]==0){continue;}
        wyn=max(wyn,Suma[i]*2);
    }
	return wyn;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 13392 KB Output is correct
2 Correct 59 ms 12544 KB Output is correct
3 Correct 65 ms 13412 KB Output is correct
4 Correct 61 ms 12680 KB Output is correct
5 Correct 72 ms 12656 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2648 KB Output is correct
2 Correct 11 ms 2912 KB Output is correct
3 Correct 14 ms 2904 KB Output is correct
4 Correct 17 ms 2908 KB Output is correct
5 Correct 18 ms 2904 KB Output is correct
6 Correct 21 ms 2908 KB Output is correct
7 Correct 18 ms 2908 KB Output is correct
8 Correct 21 ms 2972 KB Output is correct
9 Correct 22 ms 2908 KB Output is correct
10 Correct 17 ms 2904 KB Output is correct
11 Correct 15 ms 2908 KB Output is correct
12 Correct 17 ms 2904 KB Output is correct
13 Correct 18 ms 2908 KB Output is correct
14 Correct 22 ms 2908 KB Output is correct
15 Correct 23 ms 2908 KB Output is correct

Subtask #3
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 13392 KB Output is correct
2 Correct 59 ms 12544 KB Output is correct
3 Correct 65 ms 13412 KB Output is correct
4 Correct 61 ms 12680 KB Output is correct
5 Correct 72 ms 12656 KB Output is correct
6 Correct 2 ms 3416 KB Output is correct
7 Correct 40 ms 3420 KB Output is correct
8 Correct 4236 ms 4920 KB Output is correct
9 Execution timed out 5595 ms 20268 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 13392 KB Output is correct
2 Correct 59 ms 12544 KB Output is correct
3 Correct 65 ms 13412 KB Output is correct
4 Correct 61 ms 12680 KB Output is correct
5 Correct 72 ms 12656 KB Output is correct
6 Correct 1 ms 3416 KB Output is correct
7 Correct 49 ms 3040 KB Output is correct
8 Execution timed out 5587 ms 5208 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 13392 KB Output is correct
2 Correct 59 ms 12544 KB Output is correct
3 Correct 65 ms 13412 KB Output is correct
4 Correct 61 ms 12680 KB Output is correct
5 Correct 72 ms 12656 KB Output is correct
6 Correct 3 ms 2648 KB Output is correct
7 Correct 11 ms 2912 KB Output is correct
8 Correct 14 ms 2904 KB Output is correct
9 Correct 17 ms 2908 KB Output is correct
10 Correct 18 ms 2904 KB Output is correct
11 Correct 21 ms 2908 KB Output is correct
12 Correct 18 ms 2908 KB Output is correct
13 Correct 21 ms 2972 KB Output is correct
14 Correct 22 ms 2908 KB Output is correct
15 Correct 17 ms 2904 KB Output is correct
16 Correct 15 ms 2908 KB Output is correct
17 Correct 17 ms 2904 KB Output is correct
18 Correct 18 ms 2908 KB Output is correct
19 Correct 22 ms 2908 KB Output is correct
20 Correct 23 ms 2908 KB Output is correct
21 Correct 2 ms 3416 KB Output is correct
22 Correct 40 ms 3420 KB Output is correct
23 Correct 4236 ms 4920 KB Output is correct
24 Execution timed out 5595 ms 20268 KB Time limit exceeded
25 Halted 0 ms 0 KB -