oj.uz

답안 #603515

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
603515 2022-07-24T07:43:05 Z almothana05 Stranded Far From Home (BOI22_island) C++14
20 / 100
 337 ms 33872 KB 
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
queue<long long>q;
priority_queue<pair<long long, long long> >pri;
vector<long long>gr[200100];
long long num[200010] , sub[200010]  ,vis[200100] , erg[200100];
long long dfs(long long x){
    vis[x] = 1;
    for(long long i = 0 ; i < gr[x].size() ; i++){
        long long kind = gr[x][i];
        if(vis[kind] == 0){
            sub[x] += dfs(kind);
        }
    }
    return sub[x];
}
int main(){
    long long menge , numm = 0, nummer  , ed;
    cin >> menge >> ed;
    for(long long i = 0 ;i < menge ; i++){
        cin >> numm;
        num[i + 1] = numm;
        sub[i + 1] = num[i + 1];
    }
    for(long long i = 0 ; i< ed ; i++){
        cin >> numm >> nummer;
        gr[numm].push_back(nummer);
        gr[nummer].push_back(numm);
    }
    if(menge > 2000){
        dfs(1);
        erg[1] = 1;
        for(long long i = 1 ; i <=menge ; i++){
            for(long long j = 0 ; j < gr[i].size() ; j++){
                long long kind = gr[i][j];
                if(kind < i && erg[kind] == 1 && sub[i] >= num[kind]){
                    erg[i] = 1;
                }
            }
        }
        for(long long i = 1; i <= menge ; i++){
            cout << erg[i];
        }
        return 0;
    }
    for(long long i = 1 ; i <= menge ; i++){
        long long fl = 1;
        long long cmp = 0;
        vis[i] = 1;
        q.push(i);
        while(q.size()){
            long long jet = q.front();
            q.pop();
            cmp += num[jet];
            for(long long i = 0 ; i < gr[jet].size() ; i++){
                long long kind = gr[jet][i];
                pri.push({-num[kind] , kind });
            }
            while(pri.size() && -pri.top().first <= cmp){
                if(vis[pri.top().second] == 0){
                    vis[pri.top().second] = 1;
                    q.push(pri.top().second);
                }
                pri.pop();
            }
        }
        while(pri.size()){
            pri.pop();
        }
        for(long long j = 1 ; j <=menge ; j++){
            if(vis[j] == 0){
                fl = 0;
            }
            vis[j] = 0;
        }
        cout << fl ;
    }
}

Compilation message

island.cpp: In function 'long long int dfs(long long int)':
island.cpp:10:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for(long long i = 0 ; i < gr[x].size() ; i++){
      |                           ~~^~~~~~~~~~~~~~
island.cpp: In function 'int main()':
island.cpp:35:37: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |             for(long long j = 0 ; j < gr[i].size() ; j++){
      |                                   ~~^~~~~~~~~~~~~~
island.cpp:56:37: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |             for(long long i = 0 ; i < gr[jet].size() ; i++){
      |                                   ~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 158 ms 5120 KB Output is correct
5 Correct 159 ms 5132 KB Output is correct
6 Correct 208 ms 5116 KB Output is correct
7 Correct 139 ms 5116 KB Output is correct
8 Correct 138 ms 5104 KB Output is correct
9 Correct 330 ms 5164 KB Output is correct
10 Correct 136 ms 5076 KB Output is correct
11 Correct 137 ms 5116 KB Output is correct
12 Correct 103 ms 5148 KB Output is correct
13 Correct 222 ms 5116 KB Output is correct
14 Correct 127 ms 5140 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 332 ms 23716 KB Output is correct
4 Correct 232 ms 23944 KB Output is correct
5 Correct 337 ms 19684 KB Output is correct
6 Correct 294 ms 20504 KB Output is correct
7 Correct 309 ms 21412 KB Output is correct
8 Correct 316 ms 21456 KB Output is correct
9 Correct 316 ms 21516 KB Output is correct
10 Correct 215 ms 20792 KB Output is correct
11 Correct 220 ms 22152 KB Output is correct
12 Correct 273 ms 19296 KB Output is correct
13 Correct 257 ms 29972 KB Output is correct
14 Correct 265 ms 31192 KB Output is correct
15 Correct 271 ms 33872 KB Output is correct
16 Correct 210 ms 32608 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 304 ms 30048 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Incorrect 295 ms 18080 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 158 ms 5120 KB Output is correct
5 Correct 159 ms 5132 KB Output is correct
6 Correct 208 ms 5116 KB Output is correct
7 Correct 139 ms 5116 KB Output is correct
8 Correct 138 ms 5104 KB Output is correct
9 Correct 330 ms 5164 KB Output is correct
10 Correct 136 ms 5076 KB Output is correct
11 Correct 137 ms 5116 KB Output is correct
12 Correct 103 ms 5148 KB Output is correct
13 Correct 222 ms 5116 KB Output is correct
14 Correct 127 ms 5140 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 332 ms 23716 KB Output is correct
18 Correct 232 ms 23944 KB Output is correct
19 Correct 337 ms 19684 KB Output is correct
20 Correct 294 ms 20504 KB Output is correct
21 Correct 309 ms 21412 KB Output is correct
22 Correct 316 ms 21456 KB Output is correct
23 Correct 316 ms 21516 KB Output is correct
24 Correct 215 ms 20792 KB Output is correct
25 Correct 220 ms 22152 KB Output is correct
26 Correct 273 ms 19296 KB Output is correct
27 Correct 257 ms 29972 KB Output is correct
28 Correct 265 ms 31192 KB Output is correct
29 Correct 271 ms 33872 KB Output is correct
30 Correct 210 ms 32608 KB Output is correct
31 Correct 3 ms 4948 KB Output is correct
32 Incorrect 304 ms 30048 KB Output isn't correct
33 Halted 0 ms 0 KB -