oj.uz

Submission #491316

# Submission time Handle Problem Language Result Execution time Memory
491316 2021-12-01T13:21:23 Z qwerasdfzxcl Simurgh (IOI17_simurgh) C++14
19 / 100
 128 ms 4208 KB 
#include "simurgh.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF = 1e9;
int adj[505][505], n;
bool chk[505];

int calc(int p, int l, int r){
    vector<int> Q;
    for (int i=l;i<=r;i++) Q.push_back(adj[p][i]);
    int cnt = 0;
    Q.push_back(adj[0][p]);
    if (chk[p]) cnt++;

    for (int i=1;i<n;i++) if (!(l<=i && i<=r) && i!=p){
        Q.push_back(adj[0][i]);
        if (chk[i]) cnt++;
    }

    return count_common_roads(Q) - cnt;
}

std::vector<int> find_roads(int N, std::vector<int> u, std::vector<int> v) {
    //if (N==2) return {0};
    n = N;
    fill(adj[0], adj[504]+505, -1);
    for (int i=0;i<(int)u.size();i++){
        adj[u[i]][v[i]] = i;
        adj[v[i]][u[i]] = i;
    }

    vector<pair<int, int>> v1;
    vector<int> Q;
    for (int i=2;i<n;i++) Q.push_back(adj[1][i]);
    int mn = INF;
    for (int i=1;i<n;i++){
        Q.push_back(adj[0][i]);
        v1.emplace_back(i, count_common_roads(Q));
        Q.pop_back();
        mn = min(mn, v1.back().second);
    }

    int cnt = 0;
    for (auto &p:v1) if (p.second==mn) cnt++;

    vector<int> ans;
    for (auto &p:v1) if (cnt==n-1 || p.second!=mn){
        chk[p.first] = 1;
        ans.push_back(adj[0][p.first]);
    }

    //for (int i=1;i<n;i++) printf("%d ", chk[i]);
    //printf("\n");

    for (int i=1;i<n;i++){
        int prv = i;
        while(calc(i, prv+1, n-1) > 0){
            //printf("YES: %d\n", i);
            int l = prv+1, r = n-1;
            while(r-l > 0){
                int m = (l+r)>>1;
                if (calc(i, l, m) > 0) r = m;
                else l = m+1;
            }
            ans.push_back(adj[i][l]);
            prv = l;
        }
    }
    return ans;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1228 KB correct
2 Correct 1 ms 1228 KB correct
3 Correct 1 ms 1228 KB correct
4 Incorrect 1 ms 1228 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1228 KB correct
2 Correct 1 ms 1228 KB correct
3 Correct 1 ms 1228 KB correct
4 Incorrect 1 ms 1228 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1228 KB correct
2 Correct 1 ms 1228 KB correct
3 Correct 1 ms 1228 KB correct
4 Incorrect 1 ms 1228 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1228 KB correct
2 Correct 1 ms 1228 KB correct
3 Correct 67 ms 3144 KB correct
4 Correct 102 ms 4096 KB correct
5 Correct 116 ms 4192 KB correct
6 Correct 102 ms 4192 KB correct
7 Correct 117 ms 4172 KB correct
8 Correct 107 ms 4196 KB correct
9 Correct 105 ms 4164 KB correct
10 Correct 102 ms 4200 KB correct
11 Correct 101 ms 4164 KB correct
12 Correct 128 ms 4164 KB correct
13 Correct 1 ms 1228 KB correct
14 Correct 103 ms 4208 KB correct
15 Correct 100 ms 4088 KB correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1228 KB correct
2 Correct 1 ms 1228 KB correct
3 Correct 1 ms 1228 KB correct
4 Incorrect 1 ms 1228 KB WA in grader: NO
5 Halted 0 ms 0 KB -