oj.uz

Submission #1006731

# Submission time Handle Problem Language Result Execution time Memory
1006731 2024-06-24T07:52:59 Z Amr Closing Time (IOI23_closing) C++17
8 / 100
 87 ms 32340 KB 
// start at :10:36
#include "closing.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define sz size()
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef long double ld;
ll n , k;
const int M = 2e5+2;
vector<pair<ll,ll> > v[M];
ll dis[M], p[M];
vector<ll> allx, ally;
set<pair<ll,ll> > s;
void dfs(ll x, ll par,ll d)
{
    p[x] = par;
    dis[x] = d;
    for(int i = 0; i < v[x].sz; i++)
    {
         ll newn = v[x][i].F, w = v[x][i].S;
         if(newn!=par) dfs(newn,x,d+w);
    }
}
int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    n = N , k = K;
    for(int i = 0 ; i <= n; i++) v[i].clear();
    allx.clear(); ally.clear(); s.clear();
    for(int i = 0; i < n-1; i++)
    {
        ll x = U[i], y = V[i];
        v[x].push_back({y,W[i]});
        v[y].push_back({x,W[i]});
    }
    //
    dfs(X,-1,0);
    s.insert({0,X});
    ll sum = 0;
    while(1)
    {
        ll cur = s.begin()->S;
        ll w = s.begin()->F;
        s.erase(s.begin());
        if(sum+w>k) break;
        sum+=w;
        allx.push_back(w);
        for(int i = 0; i < v[cur].sz; i++)
        {
            ll newn = v[cur][i].F;
            if(newn==p[cur]) continue;
            s.insert({dis[newn],newn});
        }
    }
    //
    s.clear();
    dfs(Y,-1,0);
    s.insert({0,Y});
    sum = 0;
    while(1)
    {
        ll cur = s.begin()->S;
        ll w = s.begin()->F;
        s.erase(s.begin());
        if(sum+w>k) break;
        sum+=w;
        ally.push_back(w);
        for(int i = 0; i < v[cur].sz; i++)
        {
            ll newn = v[cur][i].F;
            if(newn==p[cur]) continue;
            s.insert({dis[newn],newn});
        }
    }
 //   for(int i = 0; i < allx.sz; i++) cout << allx[i] << " "; cout << endl;
  //  for(int i = 0; i < allx.sz; i++) cout << ally[i] << " "; cout << endl;
    for(int i = 1; i < allx.sz ;i++) allx[i] +=allx[i-1];
    for(int i = 1; i < ally.sz ;i++) ally[i] +=ally[i-1];

    ll best = 0;
    for(int i = 0; i < allx.sz; i++)
    {
        ll now = allx[i];
        ll dif = k-now;
        ll l = -1, r = ally.sz;
        while(l+1<r)
        {
            ll mid = (l+r)/2;
            if(ally[mid]<=dif) l = mid;
            else r = mid;
        }
        best = max(best,i+1+l+1);
    }


    return best;
}

Compilation message

closing.cpp: In function 'void dfs(ll, ll, ll)':
closing.cpp:22:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i = 0; i < v[x].sz; i++)
      |                      ^
closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:52:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for(int i = 0; i < v[cur].sz; i++)
      |                          ^
closing.cpp:72:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for(int i = 0; i < v[cur].sz; i++)
      |                          ^
closing.cpp:81:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int i = 1; i < allx.sz ;i++) allx[i] +=allx[i-1];
      |                      ^
closing.cpp:82:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for(int i = 1; i < ally.sz ;i++) ally[i] +=ally[i-1];
      |                      ^
closing.cpp:85:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(int i = 0; i < allx.sz; i++)
      |                      ^

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 8028 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 27588 KB Output is correct
2 Correct 72 ms 32340 KB Output is correct
3 Correct 39 ms 10576 KB Output is correct

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Incorrect 1 ms 8028 KB 1st lines differ - on the 1st token, expected: '30', found: '24'
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Incorrect 1 ms 8028 KB 1st lines differ - on the 1st token, expected: '30', found: '24'
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Incorrect 1 ms 8028 KB 1st lines differ - on the 1st token, expected: '30', found: '24'
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 8028 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 8028 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 8028 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 8028 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 8028 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -