oj.uz

답안 #379560

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
379560 2021-03-18T15:11:30 Z Habitus Flood (IOI07_flood) C++14
10 / 100
 240 ms 24932 KB 
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define dec(x, y) fixed << setprecision((y)) << (x)
#define xx first
#define yy second
#define srt(v) sort((v).begin(), (v).end())
#define srtr(v) sort((v).rbegin(), (v).rend())
#define pb push_back
#define popb pop_back
#define sz(a) (int)(a).size()
#define len(a) (int)(a).length()
#define mp make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int n, m;
vector<pair<pii, int>> tac;
vector<pii> graf[4][100010];
int pos[200010];
stack<int> dosad;
vector<int> dobre;
bool izasao, nap;
int poc;
inline bool ista(int a, int b, int c) {
    if((b<c && a==1) || (b>c && a==2)) return true;
    return false;
}
void dfs(int node, int smer) {
    if(izasao&&node==poc) {
        nap=1;
        return;
    }
    for(int s=smer+1; s<=smer+4; ++s) {
        for(auto adj:graf[s%4][node]) {
            if(pos[adj.yy]!=3 && !ista(pos[adj.yy], node, adj.xx)) {
                if(pos[adj.yy]!=0) dobre.pb(adj.yy);
                if(node<adj.xx) pos[adj.yy]=1;
                else pos[adj.yy]=2;
                dosad.push(adj.yy);
                izasao=1;
                dfs(adj.xx, (s%4)^2);
                if(nap==1) return;
            }
        }
    }
}
void gotovo() {
    while(!dosad.empty()) {
        int tren=dosad.top();
        pos[tren]=3;
        dosad.pop();
    }
}
bool cmp(pair<pii, int> &A, pair<pii, int> &B) {
    if(A.xx.xx<B.xx.xx) return true;
    if(A.xx.xx>B.xx.xx) return false;
    if(A.xx.yy>B.xx.yy) return true;
    if(A.xx.yy<B.xx.yy) return false;
    return A.yy<B.yy;
}
int main() {
    /// pos: 0 neposecena, 1 u smeru od manjeg ka vecem, 2 suprotno, 3 skroz gotova
    /// graf: 0 gore, 1 desno, 2 dole, 3 levo
    ios;
    cin >> n;
    for(int i=1; i<=n; ++i) {
        int x, y; cin >> x >> y;
        tac.pb(mp(mp(x, y), i));
    }
    cin >> m;
    for(int i=1; i<=m; ++i) {
        int u, v; cin >> u >> v;
        int kod;
        if(tac[u-1].xx.yy==tac[v-1].xx.yy) {
            if(tac[u-1].xx.xx>tac[v-1].xx.xx) kod=3;
            else kod=1;
        }
        else {
            if(tac[u-1].xx.yy<tac[v-1].xx.yy) kod=0;
            else kod=2;
        }
        graf[kod][u].pb(mp(v, i));
        graf[kod^2][v].pb(mp(u, i));
    }
    sort(tac.begin(), tac.end(), cmp);
    for(int i=0; i<n; ++i) {
        izasao=0;
        poc=tac[i].yy;
        nap=0;
        dfs(tac[i].yy, 0);
        gotovo();
    }
    cout << sz(dobre) << "\n";
    for(auto dd:dobre) {
        cout << dd << "\n";
    }
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 7 ms 9708 KB Output is correct
3 Incorrect 7 ms 9708 KB Output isn't correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 9836 KB Output isn't correct

Subtask #4
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 9708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 9708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 9708 KB Output isn't correct

Subtask #7
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 9836 KB Output isn't correct

Subtask #8
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 9836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 9836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 31 ms 12268 KB Output isn't correct

Subtask #11
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 81 ms 23724 KB Output isn't correct

Subtask #12
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 69 ms 19044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 219 ms 23524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 240 ms 24932 KB Output isn't correct
2 Halted 0 ms 0 KB -