Submission #1121744

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121744		vjudge1	Stranded Far From Home (BOI22_island)	C++17	Compilation error	0 ms	0 KiB

island

#include <bits/stdc++.h>

#define ll long long
#define all(x) x.begin(), x.end()
#define in insert
#define F first
#define S second
#define ppf pop_front
#define pb push_back
#define ppb pop_back
#define pf push_front
#define pii pair <int, int>
#define pll pair <ll, ll>
#define boost() ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define sz(x) (int)x.size()
#define int ll
using namespace std;

const int N = 2e5+123;
const ll mod = 1e9+7;

vector<int> g[N];
int a[N];
bool ans[N];
int ls[N];
int us[N];

void dfs(int v,int p){
    ls[v]=a[v];
    for(int to : g[v]){
        if(to == p)
            continue;
        dfs(to , v);
        ls[v]+=ls[to];
        
    }
}
void dfs2(int v , int p){
    if(!ans[p])
        ans[v]=0;
    else{
        ans[v]=(ls[v] >= a[p]);
    }
    for(int to : g[v]){
        if(to == p)
            continue;
        dfs2(to , v);
        
    }
}

void solve() {
    int n,m;
    cin >> n >> m;
    vector<pll> v;
    for(int i=1 ; i <= n ; i++){
        cin >> a[i];
        v.pb({a[i] , i});
    }
    
    for(int i=1 ; i <= m ; i++){
        int v,u;
        cin >> v >> u;
        g[u].pb(v);
        g[v].pb(u);
    }
    // for(int i=1 ; i <= n ; i++){
    //     cout << a[i].F << " " << a[i].S << endl;
    // }
    
    
    if(n <= 2000 && m <= 2000){
        sort(all(v));
        reverse(all(v));
        for(int i=0 ; i < n ; i++){
            int j=v[i].S;
            us[j]=j;
            set<pll> st;
            int cnt=0;
            ans[j]=0;
            
            st.in({0 , j});
            while(!st.empty()){
                auto o=*st.begin();
                st.erase(o);
                int x=o.F;
                int v=o.S;
                if(cnt < x){
                    ans[j]=0;
                    break;
                }
                if(ans[v] == 1){
                    ans[j]=1;
                    break;
                }
                cnt+=a[v];
                for(int to : g[v]){
                    if(us[to] != j){
                        us[to]=j;
                        st.in({a[to] , to});
                    }
                    
                }
                if(st.empty()){
                    ans[j]=1;
                }
            }
        }
        for(int i=1 ; i <= n ; i++){
            cout << ans[i];
        }
        return;
    }
    
    ans[0]=1;
    dfs(1 , 0);
    dfs2(1 , 0);
    for(int i=1 ; i <= n ; i++){
        cout << ans[i];
    }
    
}
/*
4 4
2 2 4 3
1 2
1 3
2 3
3 4
*/
signed main() {
    boost();
    int tt=1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}
#include <bits/stdc++.h>

#define ll long long
#define all(x) x.begin(), x.end()
#define in insert
#define F first
#define S second
#define ppf pop_front
#define pb push_back
#define ppb pop_back
#define pf push_front
#define pii pair <int, int>
#define pll pair <ll, ll>
#define boost() ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define sz(x) (int)x.size()
#define int ll
using namespace std;

const int N = 2e5+123;
const ll mod = 1e9+7;

vector<int> g[N];
int a[N];
bool ans[N];
int ls[N];
int us[N];

void dfs(int v,int p){
    ls[v]=a[v];
    for(int to : g[v]){
        if(to == p)
            continue;
        dfs(to , v);
        ls[v]+=ls[to];
        
    }
}
void dfs2(int v , int p){
    if(!ans[p])
        ans[v]=0;
    else{
        ans[v]=(ls[v] >= a[p]);
    }
    for(int to : g[v]){
        if(to == p)
            continue;
        dfs2(to , v);
        
    }
}

void solve() {
    int n,m;
    cin >> n >> m;
    vector<pll> v;
    for(int i=1 ; i <= n ; i++){
        cin >> a[i];
        v.pb({a[i] , i});
    }
    
    for(int i=1 ; i <= m ; i++){
        int v,u;
        cin >> v >> u;
        g[u].pb(v);
        g[v].pb(u);
    }
    // for(int i=1 ; i <= n ; i++){
    //     cout << a[i].F << " " << a[i].S << endl;
    // }
    
    
    if(n <= 2000 && m <= 2000){
        sort(all(v));
        reverse(all(v));
        for(int i=0 ; i < n ; i++){
            int j=v[i].S;
            us[j]=j;
            set<pll> st;
            int cnt=0;
            ans[j]=0;
            
            st.in({0 , j});
            while(!st.empty()){
                auto o=*st.begin();
                st.erase(o);
                int x=o.F;
                int v=o.S;
                if(cnt < x){
                    ans[j]=0;
                    break;
                }
                if(ans[v] == 1){
                    ans[j]=1;
                    break;
                }
                cnt+=a[v];
                for(int to : g[v]){
                    if(us[to] != j){
                        us[to]=j;
                        st.in({a[to] , to});
                    }
                    
                }
                if(st.empty()){
                    ans[j]=1;
                }
            }
        }
        for(int i=1 ; i <= n ; i++){
            cout << ans[i];
        }
        return;
    }
    
    ans[0]=1;
    dfs(1 , 0);
    dfs2(1 , 0);
    for(int i=1 ; i <= n ; i++){
        cout << ans[i];
    }
    
}
/*
4 4
2 2 4 3
1 2
1 3
2 3
3 4
*/
signed main() {
    boost();
    int tt=1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}
#include <bits/stdc++.h>

#define ll long long
#define all(x) x.begin(), x.end()
#define in insert
#define F first
#define S second
#define ppf pop_front
#define pb push_back
#define ppb pop_back
#define pf push_front
#define pii pair <int, int>
#define pll pair <ll, ll>
#define boost() ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define sz(x) (int)x.size()
#define int ll
using namespace std;

const int N = 2e5+123;
const ll mod = 1e9+7;

vector<int> g[N];
int a[N];
bool ans[N];
int ls[N];
int us[N];

void dfs(int v,int p){
    ls[v]=a[v];
    for(int to : g[v]){
        if(to == p)
            continue;
        dfs(to , v);
        ls[v]+=ls[to];
        
    }
}
void dfs2(int v , int p){
    if(!ans[p])
        ans[v]=0;
    else{
        ans[v]=(ls[v] >= a[p]);
    }
    for(int to : g[v]){
        if(to == p)
            continue;
        dfs2(to , v);
        
    }
}

void solve() {
    int n,m;
    cin >> n >> m;
    vector<pll> v;
    for(int i=1 ; i <= n ; i++){
        cin >> a[i];
        v.pb({a[i] , i});
    }
    
    for(int i=1 ; i <= m ; i++){
        int v,u;
        cin >> v >> u;
        g[u].pb(v);
        g[v].pb(u);
    }
    // for(int i=1 ; i <= n ; i++){
    //     cout << a[i].F << " " << a[i].S << endl;
    // }
    
    
    if(n <= 2000 && m <= 2000){
        sort(all(v));
        reverse(all(v));
        for(int i=0 ; i < n ; i++){
            int j=v[i].S;
            us[j]=j;
            set<pll> st;
            int cnt=0;
            ans[j]=0;
            
            st.in({0 , j});
            while(!st.empty()){
                auto o=*st.begin();
                st.erase(o);
                int x=o.F;
                int v=o.S;
                if(cnt < x){
                    ans[j]=0;
                    break;
                }
                if(ans[v] == 1){
                    ans[j]=1;
                    break;
                }
                cnt+=a[v];
                for(int to : g[v]){
                    if(us[to] != j){
                        us[to]=j;
                        st.in({a[to] , to});
                    }
                    
                }
                if(st.empty()){
                    ans[j]=1;
                }
            }
        }
        for(int i=1 ; i <= n ; i++){
            cout << ans[i];
        }
        return;
    }
    
    ans[0]=1;
    dfs(1 , 0);
    dfs2(1 , 0);
    for(int i=1 ; i <= n ; i++){
        cout << ans[i];
    }
    
}
/*
4 4
2 2 4 3
1 2
1 3
2 3
3 4
*/
signed main() {
    boost();
    int tt=1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

island.cpp:158:11: error: redefinition of 'const long long int N'
  158 | const int N = 2e5+123;
      |           ^
island.cpp:19:11: note: 'const long long int N' previously defined here
   19 | const int N = 2e5+123;
      |           ^
island.cpp:159:10: error: redefinition of 'const long long int mod'
  159 | const ll mod = 1e9+7;
      |          ^~~
island.cpp:20:10: note: 'const long long int mod' previously defined here
   20 | const ll mod = 1e9+7;
      |          ^~~
island.cpp:161:13: error: redefinition of 'std::vector<long long int> g [200123]'
  161 | vector<int> g[N];
      |             ^
island.cpp:22:13: note: 'std::vector<long long int> g [200123]' previously declared here
   22 | vector<int> g[N];
      |             ^
island.cpp:162:5: error: redefinition of 'long long int a [200123]'
  162 | int a[N];
      |     ^
island.cpp:23:5: note: 'long long int a [200123]' previously declared here
   23 | int a[N];
      |     ^
island.cpp:163:6: error: redefinition of 'bool ans [200123]'
  163 | bool ans[N];
      |      ^~~
island.cpp:24:6: note: 'bool ans [200123]' previously declared here
   24 | bool ans[N];
      |      ^~~
island.cpp:164:5: error: redefinition of 'long long int ls [200123]'
  164 | int ls[N];
      |     ^~
island.cpp:25:5: note: 'long long int ls [200123]' previously declared here
   25 | int ls[N];
      |     ^~
island.cpp:165:5: error: redefinition of 'long long int us [200123]'
  165 | int us[N];
      |     ^~
island.cpp:26:5: note: 'long long int us [200123]' previously declared here
   26 | int us[N];
      |     ^~
island.cpp:167:6: error: redefinition of 'void dfs(long long int, long long int)'
  167 | void dfs(int v,int p){
      |      ^~~
island.cpp:28:6: note: 'void dfs(long long int, long long int)' previously defined here
   28 | void dfs(int v,int p){
      |      ^~~
island.cpp:177:6: error: redefinition of 'void dfs2(long long int, long long int)'
  177 | void dfs2(int v , int p){
      |      ^~~~
island.cpp:38:6: note: 'void dfs2(long long int, long long int)' previously defined here
   38 | void dfs2(int v , int p){
      |      ^~~~
island.cpp:191:6: error: redefinition of 'void solve()'
  191 | void solve() {
      |      ^~~~~
island.cpp:52:6: note: 'void solve()' previously defined here
   52 | void solve() {
      |      ^~~~~
island.cpp:270:8: error: redefinition of 'int main()'
  270 | signed main() {
      |        ^~~~
island.cpp:131:8: note: 'int main()' previously defined here
  131 | signed main() {
      |        ^~~~
island.cpp:297:11: error: redefinition of 'const long long int N'
  297 | const int N = 2e5+123;
      |           ^
island.cpp:19:11: note: 'const long long int N' previously defined here
   19 | const int N = 2e5+123;
      |           ^
island.cpp:298:10: error: redefinition of 'const long long int mod'
  298 | const ll mod = 1e9+7;
      |          ^~~
island.cpp:20:10: note: 'const long long int mod' previously defined here
   20 | const ll mod = 1e9+7;
      |          ^~~
island.cpp:300:13: error: redefinition of 'std::vector<long long int> g [200123]'
  300 | vector<int> g[N];
      |             ^
island.cpp:22:13: note: 'std::vector<long long int> g [200123]' previously declared here
   22 | vector<int> g[N];
      |             ^
island.cpp:301:5: error: redefinition of 'long long int a [200123]'
  301 | int a[N];
      |     ^
island.cpp:23:5: note: 'long long int a [200123]' previously declared here
   23 | int a[N];
      |     ^
island.cpp:302:6: error: redefinition of 'bool ans [200123]'
  302 | bool ans[N];
      |      ^~~
island.cpp:24:6: note: 'bool ans [200123]' previously declared here
   24 | bool ans[N];
      |      ^~~
island.cpp:303:5: error: redefinition of 'long long int ls [200123]'
  303 | int ls[N];
      |     ^~
island.cpp:25:5: note: 'long long int ls [200123]' previously declared here
   25 | int ls[N];
      |     ^~
island.cpp:304:5: error: redefinition of 'long long int us [200123]'
  304 | int us[N];
      |     ^~
island.cpp:26:5: note: 'long long int us [200123]' previously declared here
   26 | int us[N];
      |     ^~
island.cpp:306:6: error: redefinition of 'void dfs(long long int, long long int)'
  306 | void dfs(int v,int p){
      |      ^~~
island.cpp:28:6: note: 'void dfs(long long int, long long int)' previously defined here
   28 | void dfs(int v,int p){
      |      ^~~
island.cpp:316:6: error: redefinition of 'void dfs2(long long int, long long int)'
  316 | void dfs2(int v , int p){
      |      ^~~~
island.cpp:38:6: note: 'void dfs2(long long int, long long int)' previously defined here
   38 | void dfs2(int v , int p){
      |      ^~~~
island.cpp:330:6: error: redefinition of 'void solve()'
  330 | void solve() {
      |      ^~~~~
island.cpp:52:6: note: 'void solve()' previously defined here
   52 | void solve() {
      |      ^~~~~
island.cpp:409:8: error: redefinition of 'int main()'
  409 | signed main() {
      |        ^~~~
island.cpp:131:8: note: 'int main()' previously defined here
  131 | signed main() {
      |        ^~~~