Submission #969063

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
969063	2024-04-24T12:58:40 Z	hirayuu_oj	Flood (IOI07_flood)	C++17	64 / 100	721 ms	26104 KB

flood

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0; i<n; i++)
#define all(x) x.begin(),x.end()
using ll=long long;


ll dir(pair<ll,ll> x,pair<ll,ll> y){
    if(x.first==y.first){
        if(x.second<y.second)return 0;
        return 2;
    }
    if(x.first<y.first)return 1;
    return 3;
}
ll wall_ind(array<pair<ll,ll>,4> wall){
    ll cnt=0;
    ll pos=-1;
    rep(i,4){
        if(wall[i].first!=-1){
            cnt++;
            pos=i;
        }
    }
    if(cnt==1)return pos;
    return -1;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll N;
    cin>>N;
    vector<pair<ll,ll>> pnt(N);
    rep(i,N){
        cin>>pnt[i].first>>pnt[i].second;
    }
    vector<array<pair<ll,ll>,4>> gr(N,{pair(-1,-1),pair(-1,-1),pair(-1,-1),pair(-1,-1)});
    ll W;
    cin>>W;
    vector<ll> ok(W,0);
    vector<pair<ll,ll>> wall(W);
    rep(i,W){
        cin>>wall[i].first>>wall[i].second;
        wall[i].first--;
        wall[i].second--;
        gr[wall[i].first][dir(pnt[wall[i].first],pnt[wall[i].second])]=pair(i,wall[i].second);
        gr[wall[i].second][dir(pnt[wall[i].second],pnt[wall[i].first])]=pair(i,wall[i].first);
    }
    vector<ll> ans;
    stack<ll> del;
    rep(i,N){
        if(wall_ind(gr[i])!=-1){
            del.push(i);
        }
    }
    while(!del.empty()){
        ll pos=del.top();
        del.pop();
        if(wall_ind(gr[pos])==-1)continue;
        ll dir=wall_ind(gr[pos]);
        ok[gr[pos][dir].first]=1;
        ans.push_back(gr[pos][dir].first);
        gr[gr[pos][dir].second][(dir+2)%4]={-1,-1};
        if(wall_ind(gr[gr[pos][dir].second])!=-1){
            del.push(gr[pos][dir].second);
        }
        gr[pos][dir]={-1,-1};
    }
    vector<array<ll,4>> vert(N,{-1,-1,-1,-1});
    ll cnt=0;
    rep(i,N){
        rep(j,4){
            if(gr[i][j].first==-1)continue;
            if(vert[i][j]!=-1)continue;
            ll pos=i;
            ll dir=j;
            while(vert[pos][dir]==-1){
                vert[pos][dir]=cnt;
                pos=gr[pos][dir].second;
                dir=(dir+3)%4;
                while(gr[pos][dir].first==-1){
                    dir++;
                    dir%=4;
                }
            }
            cnt++;
        }
    }
    vector<vector<ll>> zag(cnt);
    rep(i,W){
        if(ok[i])continue;
        ll s=vert[wall[i].first][dir(pnt[wall[i].first],pnt[wall[i].second])];
        ll t=vert[wall[i].second][dir(pnt[wall[i].second],pnt[wall[i].first])];
        zag[s].push_back(t);
        zag[t].push_back(s);
        cerr<<s<<" "<<t<<endl;
    }
    vector<pair<ll,ll>> order;
    rep(i,W){
        if(ok[i])continue;
        if(dir(pnt[wall[i].first],pnt[wall[i].second])==3){
            order.push_back({pnt[wall[i].first].second,vert[wall[i].first][3]});
        }
        if(dir(pnt[wall[i].second],pnt[wall[i].first])==3){
            order.push_back({pnt[wall[i].second].second,vert[wall[i].second][3]});
        }
    }
    sort(all(order));
    vector<ll> dist(cnt,-1);
    for(auto &[_,p]:order){
        if(dist[p]!=-1)continue;
        dist[p]=0;
        stack<ll> pos;
        pos.push(p);
        while(!pos.empty()){
            ll np=pos.top();
            pos.pop();
            for(ll i:zag[np]){
                if(dist[i]==-1){
                    dist[i]=dist[np]+1;
                    pos.push(i);
                }
            }
        }
    }
    rep(i,W){
        if(ok[i])continue;
        ll s=vert[wall[i].first][dir(pnt[wall[i].first],pnt[wall[i].second])];
        ll t=vert[wall[i].second][dir(pnt[wall[i].second],pnt[wall[i].first])];
        if(dist[s]==dist[t]){
            ans.push_back(i);
        }
    }
    sort(all(ans));
    cout<<ans.size()<<"\n";
    for(ll i:ans)cout<<i+1<<"\n";
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Incorrect	3 ms	348 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	456 KB	Output is correct

Subtask #8
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	352 KB	Output is correct
2	Incorrect	4 ms	352 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #9
0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	344 KB	Output is correct
2	Incorrect	3 ms	348 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #10
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	70 ms	4720 KB	Output is correct

Subtask #11
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	254 ms	16220 KB	Output is correct

Subtask #12
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	436 ms	20028 KB	Output is correct
2	Incorrect	689 ms	26104 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #13
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	574 ms	22840 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #14
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	721 ms	25896 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Submission #969063

Compilation message