oj.uz

답안 #54337

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
54337 2018-07-03T07:38:05 Z 노영훈(#1472) Flood (IOI07_flood) C++11
100 / 100
 298 ms 19744 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=100010, inf=2e9;

int n, m;

struct node {
    int x, y, idx;
    pii to[4]; // r, u, l, d (ccw), (ver, eidx)
} P[MX];

map<int, int> Index;

struct edge {
    int u, v;
    int state; // 0: unvisited, 2: will collapse, 3: will not collapse
} E[MX*2];

void vertex_input(){
    cin>>n;
    for(int i=1; i<=n; i++){
        int x, y; cin>>x>>y;
        P[i].x=x, P[i].y=y, P[i].idx=i;
    }
    sort(P+1, P+n+1, [](node &a, node &b){
        if(a.x==b.x) return a.y<b.y;
        return a.x<b.x;
    });
    for(int i=1; i<=n; i++)
        Index[P[i].idx]=i;
}

void edge_input(){
    cin>>m;
    for(int i=1, u, v; i<=m; i++){
        cin>>u>>v;
        u=Index[u], v=Index[v];
        E[i]={u,v,0};
        node &a=P[u], &b=P[v];
        if(a.x==b.x){
            if(a.y<b.y)
                a.to[1]=pii(v,i), b.to[3]=pii(u,i);
            if(a.y>b.y)
                a.to[3]=pii(v,i), b.to[1]=pii(u,i);
        }
        if(a.y==b.y){
            if(a.x<b.x)
                a.to[0]=pii(v,i), b.to[2]=pii(u,i);
            if(a.x>b.x)
                a.to[2]=pii(v,i), b.to[0]=pii(u,i);
        }
    }
}

bool valid(int x){
    for(int k=0; k<4; k++)
        if(E[P[x].to[k].second].state==0) return true;
    return false;
}

int found;
int dep[MX], now;
bool cur[MX];
void dfs(int v, int dir){
    // cout<<P[v].x<<' '<<P[v].y<<'\n';
    dep[v]=++now, cur[v]=true;
    for(int kk=dir+1; kk<dir+4; kk++){
        int k=kk%4;
        int x,eidx; tie(x,eidx)=P[v].to[k];
        if(eidx==0 || E[eidx].state>=2){
            continue;
        }
        if(E[eidx].state==0){
            if(cur[x]){
                E[eidx].state=2;
                found=x;
                break;
            }
            dfs(x, (k+2)%4);
            E[eidx].state=3;
        }
        if(found>0){
            E[eidx].state=2;
            if(found==v){
                found=-1;
            }
            else{
                break;
            }
        }
    }
    // cout<<'\n';
    now--;
    cur[v]=false;
}

void solve(){
    for(int i=1; i<=n; i++){
        if(!valid(i)) continue;
        found=-1, now=0;
        // cout<<"CYCLING\n";
        dfs(i, 3);
        // cout<<"DONE\n";
    }
}

void show(){
    int cnt=0;
    for(int i=1; i<=m; i++)
        if(E[i].state==3) cnt++;
    cout<<cnt<<'\n';
    for(int i=1; i<=m; i++)
        if(E[i].state==3)
            cout<<i<<'\n';
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    vertex_input();
    edge_input();
    solve();
    show();
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

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

Subtask #8
3.0 / 3.0

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

Subtask #9
3.0 / 3.0

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

Subtask #10
9.0 / 9.0

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

Subtask #11
9.0 / 9.0

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

Subtask #12
9.0 / 9.0

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

Subtask #13
9.0 / 9.0

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

Subtask #14
9.0 / 9.0

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