oj.uz

Submission #54326

# Submission time Handle Problem Language Result Execution time Memory
54326 2018-07-03T07:24:31 Z 노영훈(#1472) Flood (IOI07_flood) C++11
20 / 100
 326 ms 12172 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, 1: currently active, 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;
void dfs(int v, int dir){
    // cout<<P[v].x<<' '<<P[v].y<<'\n';
    dep[v]=++now;
    for(int kk=dir+1; kk<dir+4 + (dep[v]==1); 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){
            E[eidx].state=1;
            dfs(x, (k+2)%4);
            E[eidx].state=3;
        }
        else if(E[eidx].state==1){
            found=eidx;
            break;
        }
        if(found>0){
            E[eidx].state=2;
            if(found==eidx){
                found=-1;
            }
            else{
                break;
            }
        }
    }
    // cout<<'\n';
    now--;
}

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

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4836 KB Output is correct
2 Correct 5 ms 4884 KB Output is correct
3 Correct 5 ms 4884 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 4884 KB Output isn't correct

Subtask #4
0 / 3.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4912 KB Output is correct
2 Incorrect 6 ms 4912 KB Output isn't correct

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 4912 KB Output isn't correct

Subtask #7
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4944 KB Output isn't correct

Subtask #8
0 / 3.0

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

Subtask #9
0 / 3.0

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

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 6480 KB Output isn't correct

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 97 ms 11952 KB Output isn't correct

Subtask #12
0 / 9.0

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

Subtask #13
0 / 9.0

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

Subtask #14
0 / 9.0

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