Submission #746132

#	Time	Username	Problem	Language	Result	Execution time	Memory
746132		idas	Fire drill (LMIO18_sauga)	C++17	6.16 / 100	1039 ms	11716 KiB

sauga

#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define sz(x) ((int)((x).size()))
#define le(vec) vec[vec.size()-1]
#define all(x) (x).begin(), (x).end()
#define TSTS int ttt; cin >> ttt; while(ttt--) solve()
#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, begin, end) for(int i = (begin); i < (end); i++)

using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;

const int INF=1e9, MOD=1e9+7, mod=998244353;
const ll LINF=1e18;

void setIO()
{
    FAST_IO;
}

void setIO(string s)
{
    FAST_IO;
    freopen((s+".in").c_str(), "r", stdin);
    freopen((s+".out").c_str(), "w", stdout);
}

const int N=1e3+10;
int t, n, s, vis[N], adj[N];
bool v[N];
vi ad[N], re[N];

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int ops, C;
void go(int u)
{
    int nxt=u;
    while(adj[nxt]!=0){
        if(ops>=C) break;
        ++ops;

        u=nxt;
        vis[u]++;
        int in=rng()%adj[u];

        FOR(i, 0, in)
        {
            if(v[ad[u][i]]) ++in;
        }

        nxt=ad[u][in];
    }
}

void err_vec(vi &vec, int er)
{
    vi nw;
    FOR(i, 0, sz(vec))
    {
        if(vec[i]==er) continue;
        nw.pb(vec[i]);
    }
    vec=nw;
}

void err(int u)
{
    v[u]=true;
    for(auto it : re[u]) adj[it]--;
}

int main()
{
    setIO();
    cin >> t >> n >> s;
    FOR(i, 0, n)
    {
        int x; cin >> x;
        FOR(j, 0, x)
        {
            int b; cin >> b; --b;
            ad[i].pb(b);
            re[b].pb(i);
            adj[i]++;
        }
    }

    vi nodes; FOR(i, 0, n) nodes.pb(i);

    C=int(1e7)/n;
    while(!nodes.empty()){
        FOR(i, 0, n) vis[i]=0;
        ops=0;

        vi nw;
        FOR(i, 0, sz(nodes))
        {
            if(adj[nodes[i]]>0) nw.pb(nodes[i]);
            else{
                int er=nodes[i];

                err(er);

                cout << er+1 << '\n';
            }
        }
        nodes=nw;

        if(nodes.empty()) break;

        while(ops<C){
            int rnd=nodes[rng()%sz(nodes)];
            go(rnd);
        }

//        cout << "sus" << endl;

        int mx=-1;
        FOR(i, 0, n) mx=max(mx, vis[i]);

        FOR(i, 0, n)
        {
            if(vis[i]==mx){
                err_vec(nodes, i);

                err(i);

                cout << i+1 << '\n';
            }
        }

        nw.clear();
        FOR(i, 0, sz(nodes))
        {
            if(adj[nodes[i]]>0) nw.pb(nodes[i]);
            else{
                int er=nodes[i];

                err(er);

                cout << er+1 << '\n';
            }
        }
        nodes=nw;
    }
}

Compilation message (stderr)

sauga.cpp: In function 'void setIO(std::string)':
sauga.cpp:32:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     freopen((s+".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sauga.cpp:33:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     freopen((s+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6.15960099751 / 100