oj.uz

Submission #825285

# Submission time Handle Problem Language Result Execution time Memory
825285 2023-08-14T16:43:30 Z winter0101 Designated Cities (JOI19_designated_cities) C++14
23 / 100
 2000 ms 21620 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
#define pll pair<long long,long long>
#define eb emplace_bac
const int maxn=2e5+9;
vector<pil>a[maxn];
long long b[maxn];
long long c[maxn];
long long sum=0;
long long dfs(int u,int par){
long long dd=0;
for (auto v:a[u]){
    if (v.fi==par)continue;
    sum+=v.se;
    dd=max(dd,v.se+dfs(v.fi,u));
}
return dd;
}
long long dep[maxn];
long long mx=0;
bool vis[maxn];
int p[maxn];
void del(int u){
vis[u]=1;
while (u){
    u=p[u];
    if (vis[u])return;
    vis[u]=1;
}
}
void redfs(int u,int par){
if (vis[u])dep[u]=0;
mx=max(mx,dep[u]);
for (auto v:a[u]){
    if (v.fi==par)continue;
    p[v.fi]=u;
    dep[v.fi]=dep[u]+v.se;
    redfs(v.fi,u);
}
}
long long xxx[maxn];
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    int n;
    cin>>n;
    for1(i,1,n-1){
    int u,v;
    long long x,y;
    cin>>u>>v>>x>>y;
    a[u].pb({v,x});
    a[v].pb({u,y});
    }
    xxx[1]=1e18;
    for1(i,1,n){
    sum=0;
    c[i]-=dfs(i,0);
    xxx[1]=min(xxx[1],sum);
    b[i]=sum;
    c[i]+=sum;
    }
    int root=-1;
    for1(i,1,n){
    bool fl=true;
    if (sz(a[i])>1)continue;
    for1(j,1,n){
    if (i==j)continue;
    if (c[i]>c[j]){
        fl=false;
        break;
    }
    }
    if (!fl)continue;
    root=i;
    break;
    }
    long long dd=b[root];
    for1(i,2,n){
    mx=0;
    redfs(root,0);
    dd-=mx;
    for1(j,1,n){
    if (dep[j]==mx){
        del(j);
        break;
    }
    }
    xxx[i]=dd;
    //cout<<i<<" "<<dd<<'\n';
    }
    int q;
    cin>>q;
    for1(i,1,q){
    int x;
    cin>>x;
    cout<<xxx[x]<<'\n';
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4968 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 5028 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 2 ms 5036 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Execution timed out 2069 ms 19320 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Execution timed out 2078 ms 21620 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4968 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 5028 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 2 ms 5036 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Correct 72 ms 5220 KB Output is correct
14 Correct 100 ms 5396 KB Output is correct
15 Correct 67 ms 5248 KB Output is correct
16 Correct 70 ms 5224 KB Output is correct
17 Correct 90 ms 5204 KB Output is correct
18 Correct 68 ms 5220 KB Output is correct
19 Correct 82 ms 5264 KB Output is correct
20 Correct 78 ms 5264 KB Output is correct
21 Correct 72 ms 5244 KB Output is correct
22 Correct 76 ms 5220 KB Output is correct
23 Correct 67 ms 5252 KB Output is correct
24 Correct 44 ms 5224 KB Output is correct
25 Correct 88 ms 5376 KB Output is correct
26 Correct 42 ms 5204 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Execution timed out 2069 ms 19320 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4968 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 2 ms 5028 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 2 ms 5036 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Execution timed out 2069 ms 19320 KB Time limit exceeded
14 Halted 0 ms 0 KB -