oj.uz

답안 #994890

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
994890 2024-06-08T08:12:53 Z 김은성(#10865) 봉쇄 시간 (IOI23_closing) C++17
9 / 100
 298 ms 46804 KB 
#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<pair<int, ll> > graph[200009];
ll distx[200009], disty[200009];
bool chx[25], chy[25];
vector<int> routex[25], routey[25];
void dfsx(int v, ll* dist, ll cur, vector<int> path){
    if(dist[v] != -1)
        return;
    distx[v] = cur;
    path.push_back(v);
    routex[v] = path;
    int i;
    for(i=0; i<graph[v].size(); i++)
        dfsx(graph[v][i].first, dist, cur + graph[v][i].second, path);
}

void dfsy(int v, ll* dist, ll cur, vector<int> path){
    if(dist[v] != -1)
        return;
    disty[v] = cur;
    path.push_back(v);
    routey[v] = path;
    int i;
    for(i=0; i<graph[v].size(); i++)
        dfsy(graph[v][i].first, dist, cur + graph[v][i].second, path);
}
int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W){
    int i, j, ans=0;
    for(i=0; i<N; i++){
        graph[i].clear();
        distx[i] = -1;
        disty[i] = -1;
    }
    for(i=0; i<N-1; i++){
        graph[U[i]].push_back(make_pair(V[i], W[i]));
        graph[V[i]].push_back(make_pair(U[i], W[i]));
    }
    dfsx(X, distx, 0, {});
    dfsy(Y, disty, 0, {});
    for(i=0; i<(1<<N); i++){
        memset(chx, 0, sizeof(chx));
        memset(chy, 0, sizeof(chy));
        ll cur = 0;
        int cnt = 0;
        for(j=0; j<N; j++){
            if(i & (1<<j)){
                for(int k=0; k<routex[j].size(); k++)
                    chx[routex[j][k]] = 1;
                for(int k=0; k<routey[j].size(); k++)
                    chy[routey[j][k]] = 1;
                cur -= min(distx[j], disty[j]);
            }
        }
        vector<ll> temp;
        for(j=0; j<N; j++){
            if(chx[j]){
                cur += distx[j];
                cnt++;
            }
            else
                temp.push_back(distx[j]);
        }
        for(j=0; j<N; j++){
            if(chy[j]){
                cur += disty[j];
                cnt++;
            }
            else
                temp.push_back(disty[j]);
        }
        sort(temp.begin(), temp.end());
        ll now=cur;
        if(cur > K)
            continue;
        for(j=0; j<temp.size(); j++){
            now += temp[j];
            if(now > K)
                break;
        }
        ans = max(ans, j + cnt);
    }
    return ans;
}

Compilation message

closing.cpp: In function 'void dfsx(int, ll*, ll, std::vector<int>)':
closing.cpp:16:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(i=0; i<graph[v].size(); i++)
      |              ~^~~~~~~~~~~~~~~~
closing.cpp: In function 'void dfsy(int, ll*, ll, std::vector<int>)':
closing.cpp:27:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(i=0; i<graph[v].size(); 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:51:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |                 for(int k=0; k<routex[j].size(); k++)
      |                              ~^~~~~~~~~~~~~~~~~
closing.cpp:53:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |                 for(int k=0; k<routey[j].size(); k++)
      |                              ~^~~~~~~~~~~~~~~~~
closing.cpp:79:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for(j=0; j<temp.size(); j++){
      |                  ~^~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8024 KB Output is correct

Subtask #1
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 76 ms 46804 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8028 KB Output is correct
2 Correct 225 ms 8076 KB Output is correct
3 Correct 235 ms 8024 KB Output is correct
4 Correct 254 ms 8072 KB Output is correct
5 Correct 125 ms 8072 KB Output is correct
6 Runtime error 7 ms 15960 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8028 KB Output is correct
2 Correct 225 ms 8076 KB Output is correct
3 Correct 235 ms 8024 KB Output is correct
4 Correct 254 ms 8072 KB Output is correct
5 Correct 125 ms 8072 KB Output is correct
6 Runtime error 7 ms 15960 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8028 KB Output is correct
2 Correct 225 ms 8076 KB Output is correct
3 Correct 235 ms 8024 KB Output is correct
4 Correct 254 ms 8072 KB Output is correct
5 Correct 125 ms 8072 KB Output is correct
6 Runtime error 7 ms 15960 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8024 KB Output is correct
2 Correct 1 ms 8028 KB Output is correct
3 Correct 225 ms 8076 KB Output is correct
4 Correct 235 ms 8024 KB Output is correct
5 Correct 254 ms 8072 KB Output is correct
6 Correct 125 ms 8072 KB Output is correct
7 Correct 2 ms 8024 KB Output is correct
8 Correct 2 ms 8028 KB Output is correct
9 Correct 2 ms 8028 KB Output is correct
10 Correct 88 ms 8028 KB Output is correct
11 Correct 141 ms 8280 KB Output is correct
12 Correct 8 ms 8028 KB Output is correct
13 Correct 279 ms 8028 KB Output is correct
14 Correct 126 ms 8028 KB Output is correct
15 Correct 66 ms 8280 KB Output is correct
16 Correct 58 ms 8024 KB Output is correct
17 Correct 61 ms 8028 KB Output is correct
18 Correct 126 ms 8024 KB Output is correct
19 Correct 259 ms 8028 KB Output is correct
20 Correct 68 ms 8024 KB Output is correct
21 Correct 59 ms 8024 KB Output is correct
22 Correct 298 ms 8028 KB Output is correct
23 Correct 252 ms 8024 KB Output is correct
24 Correct 69 ms 8024 KB Output is correct

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8024 KB Output is correct
2 Correct 1 ms 8028 KB Output is correct
3 Correct 225 ms 8076 KB Output is correct
4 Correct 235 ms 8024 KB Output is correct
5 Correct 254 ms 8072 KB Output is correct
6 Correct 125 ms 8072 KB Output is correct
7 Runtime error 7 ms 15960 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8024 KB Output is correct
2 Correct 1 ms 8028 KB Output is correct
3 Correct 225 ms 8076 KB Output is correct
4 Correct 235 ms 8024 KB Output is correct
5 Correct 254 ms 8072 KB Output is correct
6 Correct 125 ms 8072 KB Output is correct
7 Runtime error 7 ms 15960 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8024 KB Output is correct
2 Correct 1 ms 8028 KB Output is correct
3 Correct 225 ms 8076 KB Output is correct
4 Correct 235 ms 8024 KB Output is correct
5 Correct 254 ms 8072 KB Output is correct
6 Correct 125 ms 8072 KB Output is correct
7 Runtime error 7 ms 15960 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8024 KB Output is correct
2 Correct 1 ms 8028 KB Output is correct
3 Correct 225 ms 8076 KB Output is correct
4 Correct 235 ms 8024 KB Output is correct
5 Correct 254 ms 8072 KB Output is correct
6 Correct 125 ms 8072 KB Output is correct
7 Runtime error 7 ms 15960 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -