Submission #152546

#	Time	Username	Problem	Language	Result	Execution time	Memory
152546		stefdasca	Flood (IOI07_flood)	C++14	100 / 100	236 ms	29032 KiB

flood

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 3 / 3
• Subtask 5: 10 / 10
• Subtask 6: 3 / 3
• Subtask 7: 3 / 3
• Subtask 8: 3 / 3
• Subtask 9: 3 / 3
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9
• Subtask 12: 9 / 9
• Subtask 13: 9 / 9
• Subtask 14: 9 / 9