oj.uz

Submission #980192

# Submission time Handle Problem Language Result Execution time Memory
980192 2024-05-12T00:53:51 Z FZ_Melo Closing Time (IOI23_closing) C++17
0 / 100
 1000 ms 219088 KB 
#include "closing.h"
#include <bits/stdc++.h>
#include <vector>
#include <queue>
using namespace std;

struct ari{
    int node;
    long long w;
};

struct tpos{
    int node;
    long long cnt;
    bool x;
};

bool operator <(const tpos &a, const tpos &b){
    return a.cnt>b.cnt;
}

int n;
long long k;
long long cnt;
int ans;
long long memo[200000];
vector<vector<ari>> adj;
priority_queue<tpos> q;

void dfs(){
    tpos t, ta;
    while(!q.empty() && cnt<k){
        t=q.top(); q.pop();
        if(memo[t.node]!=0){
            if(memo[t.node]<t.cnt){
                if(cnt+t.cnt-memo[t.node]<=k){
                    cnt+=t.cnt-memo[t.node];
                    memo[t.node]=t.cnt;
                }
            }
        }
        else{
            if(cnt+t.cnt<=k){
                cnt+=t.cnt;
                memo[t.node]=t.cnt;
            }
            else
                continue;
        }
        ans++;
        for(auto h: adj[t.node]){
            q.push({h.node, t.cnt+h.w});
        }
    }
    while(!q.empty())
        q.pop();
}

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;
    ans=2;
    cnt=0;
    adj.clear();
    adj.resize(n);
    for(int i=0; i<n; i++)
        memo[i]=0;
    for(int i=0; i<n-1; i++){
        adj[U[i]].push_back({V[i], W[i]});
        adj[V[i]].push_back({U[i], W[i]});
    }
    for(int i=0; i<adj[X].size(); i++){
        q.push({adj[X][i].node, adj[X][i].w});
    }
    for(int i=0; i<adj[Y].size(); i++){
        q.push({adj[Y][i].node, adj[Y][i].w});
    }
    dfs();
    return ans;
}

Compilation message

closing.cpp: In function 'void dfs()':
closing.cpp:31:13: warning: unused variable 'ta' [-Wunused-variable]
   31 |     tpos t, ta;
      |             ^~
closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:73:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ari>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(int i=0; i<adj[X].size(); i++){
      |                  ~^~~~~~~~~~~~~~
closing.cpp:76:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ari>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i=0; i<adj[Y].size(); i++){
      |                  ~^~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1062 ms 219088 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

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

Subtask #3
0.0 / 12.0

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

Subtask #4
0.0 / 14.0

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

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Execution timed out 1057 ms 197832 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Execution timed out 1057 ms 197832 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Execution timed out 1057 ms 197832 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Execution timed out 1057 ms 197832 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Execution timed out 1057 ms 197832 KB Time limit exceeded
4 Halted 0 ms 0 KB -