oj.uz

답안 #757735

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
757735 2023-06-13T17:03:31 Z karrigan Stranded Far From Home (BOI22_island) C++17
0 / 100
 375 ms 524288 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
using pii=pair<int,int>;
using pli=pair<long long,int>;
using pil=pair<int,long long>;
using pll=pair<long long,long long>;
const int maxn=2e5+9;
int lab[maxn*2];
vector<int>a[maxn*2];
int findset(int u){
if (lab[u]==u)return u;
return lab[u]=findset(lab[u]);
}
int nnode=0;
int n,m;
int mx[maxn*2];
void unite(int u,int v,int w){
u=findset(u),v=findset(v);
if (u==v)return;
lab[++nnode]=nnode;
a[nnode].pb(u);
a[nnode].pb(v);
//cout<<nnode<<" "<<u<<'\n';
//cout<<nnode<<" "<<v<<'\n';
mx[nnode]=w;
lab[u]=nnode;
lab[v]=nnode;
}
int b[maxn];
int d[maxn];
struct edg{
    int u,v;
    bool operator <(const edg &p)const {
    return max(b[u],b[v])<max(b[p.u],b[p.v]);
    }
}c[maxn];
long long sub[maxn*2];
int st[maxn*2][21];
void dfs(int u){
for (auto v:a[u]){
    st[v][0]=u;
    for1(j,1,20){
    st[v][j]=st[st[v][j-1]][j-1];
    }
    dfs(v);
    sub[u]+=sub[v];
}
}
signed main(){
    srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("usaco.INP","r",stdin);
    //freopen("usaco.OUT","w",stdout);
    cin>>n>>m;
    for1(i,1,n){
    cin>>b[i];
    lab[i]=i;
    d[i]=b[i];
    mx[i]=b[i];
    sub[i]+=b[i];
    }
    sort(d+1,d+1+n);
    for1(i,1,m){
    cin>>c[i].u>>c[i].v;
    }
    sort(c+1,c+1+m);
    nnode=n;
    for1(i,1,m){
    unite(c[i].u,c[i].v,max(b[c[i].u],b[c[i].v]));
    //cout<<c[i].u<<" "<<c[i].v<<'\n';
    }
    dfs(nnode);
    for1(i,1,n){
    long long nn=b[i];
    bool fl=false;
    while (true){
    //cerr<<nn<<'\n';
    int id=upper_bound(d+1,d+1+n,nn)-d;
    if (id==1+n){
        fl=true;
        break;
    }
    int kaka=i;
    for2(j,20,0){
    if (st[kaka][j]==0)continue;
    if (mx[st[kaka][j]]<=nn){
        kaka=st[kaka][j];
    }
    }
    //cout<<sub[kaka]<<'\n';
    long long newsum=sub[kaka];
    int id2=upper_bound(d+1,d+1+n,newsum)-d;
    if (id==id2){
        break;
    }
    nn=newsum;
    }
    cout<<fl;
    }
}

Compilation message

island.cpp: In function 'void unite(int, int, int)':
island.cpp:32:5: warning: operation on 'nnode' may be undefined [-Wsequence-point]
   32 | lab[++nnode]=nnode;
      |     ^~~~~~~
island.cpp:32:5: warning: operation on 'nnode' may be undefined [-Wsequence-point]

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Runtime error 375 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Runtime error 371 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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