oj.uz

Submission #152546

# Submission time Handle Problem Language Result Execution time Memory
152546 2019-09-08T10:54:59 Z stefdasca Flood (IOI07_flood) C++14
100 / 100
 236 ms 29032 KB 
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007

using namespace std;

vector<pair<pair<int, int>, int> >v;
multiset<pair<pair<int, int>, int > >ms;
int n, m;
vector<pair<int, int> >mch[100005][5];
bool viz[100005];
vector<int> ans;
pair<int, int> p[100005];
int direction(pair<int, int> a, pair<int, int> b)
{
    if(b.fi == a.fi)
    {
        if(b.se > a.se)
            return 0;
        return 2;
    }
    if(b.fi > a.fi)
        return 1;
    return 3;
}
int go(int nod, int dir)
{
    if (viz[nod])
        return nod;
    viz[nod] = 1;
    for(int i = 0; i < 4; ++i)
    {
        int nxt = ((dir + 1) - i + 4) % 4;
        if(mch[nod][nxt].empty())
            continue;
        auto ed = mch[nod][nxt].front();
        mch[nod][nxt].clear();
        int vecin = ed.se;
        mch[vecin][(nxt + 2) % 4].clear();
        int loop = go(vecin, nxt);
        if(!loop)
        {
            ans.pb(ed.fi);
            continue;
        }
        if (loop != nod)
        {
            viz[nod] = 0;
            return loop;
        }
    }
    viz[nod] = 0;
    return 0;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i = 1; i <= n; ++i)
    {
        cin >> p[i].fi >> p[i].se;
        v.pb({p[i], i});
    }
    cin >> m;
    for(int i = 1; i <= m; ++i)
    {
        int a, b;
        cin >> a >> b;
        mch[a][direction(p[a], p[b])].pb({i, b});
        mch[b][direction(p[b], p[a])].pb({i, a});
    }
    sort(v.begin(), v.end());
    for(int i = 0; i < v.size(); ++i)
        go(v[i].se, 0);
    cout << ans.size() << '\n';
    for(int i = 0; i < ans.size(); ++i)
        cout << ans[i] << '\n';
    return 0;
}

Compilation message

flood.cpp: In function 'int main()':
flood.cpp:78:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v.size(); ++i)
                    ~~^~~~~~~~~~
flood.cpp:81:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < ans.size(); ++i)
                    ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12024 KB Output is correct
2 Correct 13 ms 12024 KB Output is correct
3 Correct 13 ms 12024 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12028 KB Output is correct
2 Correct 13 ms 12152 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12152 KB Output is correct
2 Correct 12 ms 12024 KB Output is correct

Subtask #6
3.0 / 3.0

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

Subtask #7
3.0 / 3.0

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

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12152 KB Output is correct
2 Correct 13 ms 12232 KB Output is correct

Subtask #9
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12068 KB Output is correct
2 Correct 15 ms 12152 KB Output is correct

Subtask #10
9.0 / 9.0

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

Subtask #11
9.0 / 9.0

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

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 21800 KB Output is correct
2 Correct 211 ms 27032 KB Output is correct

Subtask #13
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 25288 KB Output is correct
2 Correct 236 ms 27512 KB Output is correct

Subtask #14
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 26888 KB Output is correct
2 Correct 176 ms 29032 KB Output is correct