— Dark mode

NOI 2019 Open

Distance Code

  • Start: N/A
  • End: N/A
  • Contest has ended
CSES - NOI 2019 Open - Results
Submission details
Task:Distance Code
Sender:toonewbie
Submission time:2019-03-09 20:11:59 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.02 s1, 2, 3details
#2ACCEPTED0.03 s1, 2, 3details
#3ACCEPTED0.02 s1, 2, 3details
#4ACCEPTED0.02 s1, 2, 3details
#50.03 s1, 2, 3details
#6ACCEPTED0.02 s1, 2, 3details
#7ACCEPTED0.02 s1, 2, 3details
#8ACCEPTED0.02 s1, 2, 3details
#90.02 s1, 2, 3details
#100.02 s1, 2, 3details
#110.03 s1, 2, 3details
#12ACCEPTED0.03 s2, 3details
#130.03 s2, 3details
#140.04 s2, 3details
#150.03 s2, 3details
#16--3details
#17--3details
#18--3details
#19--3details
#20ACCEPTED0.02 s1, 2, 3details

Compiler report

input/code.cpp: In function 'int is_prime(int)':
input/code.cpp:50:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     if (n <= 1 || n > 3 && (n % 2 == 0 || n % 3 == 0))
                   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Code

/****Author: Barish Namazov****/
#include <bits/stdc++.h>
 
using namespace std;
 
/***TEMPLATE***/
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
 
#define F first
#define S second
#define pb push_back
 
#define endl '\n'
 
const int max4 = 10004;
const int maxx = 100005;
const int max6 = 1000006;
const int lg5 = 17;
 
const int INF = 2 * 1000000007;
const long long INFLL = 4LL * 1000000000 * 1000000000;
 
/***************/
 
int powmod (int a, int b, int mod) {
    int res = 1; a %= mod;
    for (; b; b >>= 1) {
        if (b & 1) {
            res = 1LL * res * a % mod;
        }
        a = 1LL * a * a % mod;
    }
    return res;
}
 
int gcd (int a, int b) {
    while (b > 0) {
        int t = a % b;
        a = b, b = t;
    }
    return a;
}
 
int lcm (int a, int b) {
    return (a / gcd (a, b)) * b;
}
 
int is_prime (int n) {
    if (n <= 1 || n > 3 && (n % 2 == 0 || n % 3 == 0))
        return 0;
    for (int i = 5, t = 2; i * i <= n; i += t, t = 6 - t)
        if (n % i == 0)
            return 0;
    return 1;
}
 
/******Don't forget to use long long when needed!!******/
 
vector <int> g[maxx];
int par[maxx][18], lvl[maxx];
 
vector <pair <int, int>> nds;
void solve_1(int v, int p = 0, int d = 0) {
    nds.pb({d, v});
    for (int i : g[v]) {
        if (i != p) {
            solve_1(i, v, d - 1);
        }
    }
}
 
vector <int> can;
void dfs(int v, int d, int p = 0) {
    if (d == 0) {
        can.pb(v);
        return;
    }
    for (int j = g[v].size() - 1; j >= 0; j--) {
        int i = g[v][j];
        if (i == p) continue;
        dfs(i, d - 1, v);
        //if (t != 0) return t;
    }
    //return 0;
}
 
int f[maxx], mxlf[maxx];
set <int> s[maxx];
int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios_base :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t, n;
    cin >> t >> n;
    if (t == 1) {
        int a, b;
        for (int i = 1; i < n; i++) {
            cin >> a >> b;
            g[a].pb(b), g[b].pb(a);
        }
        solve_1(1);
        sort(all(nds));
        for (auto i : nds) {
            cout << i.S << " ";
        }
        cout << endl;
        return 0;
    }
    vector <int> d(n);
    for (int i = 1; i < n; i++) {
        cin >> d[i];
    }
    int cur = 1;
    for (int i = n - 1; i >= 1; i--) {
        dfs(cur, d[i] - 1);
        cur++;
        int nd;
        if (i == 1) nd = can[0];
        else {
            vector <int> gg = can;
            can.clear();
            for (int j : gg) {
                g[j].pb(cur); g[cur].pb(j);
                dfs(j, d[i - 1] - 1);
                g[j].pop_back(), g[cur].pop_back();
                if (can.size() > 0) {
                    nd = j; break;
                }
                can.clear();
            }
        }
        g[nd].pb(cur);
        g[cur].pb(nd);
        can.clear();
    }
    /*
    for (int i = n - 1; i >= 1; i--) {
        int x = d[i] - 1;
        int now = cur;
        for (int j = 0; j < 18; j++) {
            if (x & (1 << j)) {
                now = par[now][j];
            }
        }
        if (now != 0) {
            //cout << cur << " " << now << endl;
            g[now].pb(++cur);
            lvl[cur] = lvl[now] + 1;
            if (now == 1) {
                f[cur] = cur;
                s[cur].insert(cur);
            } else {
                s[f[now]].insert(cur);
                f[cur] = f[now];
            }
            if (lvl[mxlf[f[cur]]] < lvl[cur]) {
                mxlf[f[cur]] = cur;
            }
            par[cur][0] = now;
            for (int j = 1; j < 18; j++) {
                par[cur][j] = par[par[cur][j - 1]][j - 1];
            }
            continue;
        }
        x -= lvl[cur];
        int go = 0;
        for (int j : g[1]) {
            if (lvl[mxlf[j]] >= x && s[j].count(now) == 0) {
                go = mxlf[j]; break;
            }
        }
        //cout << go << endl;
        x = lvl[go] - x;
        for (int j = 0; j < 18; j++) {
            if (x & (1 << j)) {
                go = par[go][j];
            }
        }
        now = go;
        //cout << cur << " " << now << endl;
        g[now].pb(++cur);
        lvl[cur] = lvl[now] + 1;
        if (now == 1) {
            f[cur] = cur;
            s[cur].insert(cur);
        } else {
            s[f[now]].insert(cur);
            f[cur] = f[now];
        }
        if (lvl[mxlf[f[cur]]] < lvl[cur]) {
            mxlf[f[cur]] = cur;
        }
        par[cur][0] = now;
        for (int j = 1; j < 18; j++) {
            par[cur][j] = par[par[cur][j - 1]][j - 1];
        }
    } //cout << endl;
    */
    map <pair <int, int>, int> mp;
    for (int i = 1; i <= n; i++) {
        for (int j : g[i]) {
            if (!mp.count({i, j})) {
                cout << i << " " << j << endl;
                mp[{i, j}]; mp[{j, i}];
            }
        }
    }
    return 0;
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
2
2 1
view save

correct output
(empty)

user output
1 2
view save

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
3
3 1
2 1
view save

correct output
(empty)

user output
1 2
1 3
view save

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
4
3 2
2 1
4 1
view save

correct output
(empty)

user output
1 2
1 3
3 4
view save

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
4
2 3
3 4
1 3
view save

correct output
(empty)

user output
1 2
2 3
2 4
view save

Test 5

Group: 1, 2, 3

Verdict:

input
1
5
3 5
4 1
1 3
...
view save

correct output
(empty)

user output
1 2
1 3
1 4
3 5
view save

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
5
3 2
3 4
5 1
...
view save

correct output
(empty)

user output
1 2
1 3
3 4
3 5
view save

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
5
4 3
1 4
4 2
...
view save

correct output
(empty)

user output
1 2
2 3
2 4
2 5
view save

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
10
9 3
8 9
2 9
...
view save

correct output
(empty)

user output
1 2
2 3
2 4
2 5
2 6
...
view save

Test 9

Group: 1, 2, 3

Verdict:

input
1
10
9 2
5 8
7 1
...
view save

correct output
(empty)

user output
1 2
1 3
1 4
1 5
1 6
...
view save

Test 10

Group: 1, 2, 3

Verdict:

input
1
10
10 4
9 1
4 7
...
view save

correct output
(empty)

user output
1 2
1 3
1 4
4 5
4 6
...
view save

Test 11

Group: 1, 2, 3

Verdict:

input
1
10
2 6
4 3
3 5
...
view save

correct output
(empty)

user output
1 2
1 3
1 4
1 5
1 6
...
view save

Test 12

Group: 2, 3

Verdict: ACCEPTED

input
1
500
10 6
6 255
6 428
...
view save

correct output
(empty)

user output
1 2
2 3
2 4
2 5
2 6
...
Truncated

Test 13

Group: 2, 3

Verdict:

input
1
500
152 466
451 313
158 479
...
view save

correct output
(empty)

user output
1 2
1 3
1 4
1 5
1 6
...
Truncated

Test 14

Group: 2, 3

Verdict:

input
1
500
109 440
330 190
443 161
...
view save

correct output
(empty)

user output
1 2
1 3
2 4
2 5
2 6
...
Truncated

Test 15

Group: 2, 3

Verdict:

input
1
500
144 373
257 233
341 318
...
view save

correct output
(empty)

user output
1 2
1 3
1 4
1 5
1 6
...
Truncated

Test 16

Group: 3

Verdict:

input
1
100000
54983 75172
93807 75172
44082 75172
...
view save

correct output
(empty)

user output
(empty)

Test 17

Group: 3

Verdict:

input
1
100000
88863 19059
86423 76688
98536 95984
...
view save

correct output
(empty)

user output
(empty)

Test 18

Group: 3

Verdict:

input
1
100000
59979 6389
19097 24999
27846 82330
...
view save

correct output
(empty)

user output
(empty)

Test 19

Group: 3

Verdict:

input
1
100000
58761 66001
25102 51081
98625 67861
...
view save

correct output
(empty)

user output
(empty)

Test 20

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
6
2 1
3 2
4 2
...
view save

correct output
(empty)

user output
1 2
2 3
2 4
4 5
4 6
view save

Tasks

A Distance Code-B Thieves and Prisons-C Graph Ordering-

Submissions (toonewbie)

2:42:08 02:37:29 212:31:55 211:36:47 211:32:19 211:20:24 211:14:52 01:07:53 0