oj.uz

Submission #560860

# Submission time Handle Problem Language Result Execution time Memory
560860 2022-05-12T04:00:18 Z Yazan_Alattar Dijamant (COI16_dijament) C++14
100 / 100
 303 ms 11216 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 1007;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const double eps = 1e-6;
const int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0};
const int block = 320;

map <string, int> mp;
string s[M];
vector <int> roots[M], v[M];
int n, dep[M][M], p[M][M], cmproot;

bool cmp(int a, int b){
    return dep[a][cmproot] > dep[b][cmproot];
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; ++i){
        vector <int> tmp; bool ok = 1;
        cin >> s[i];

        if(mp[s[i]]) ok = 0;
        else mp[s[i]] = i;
        int node = mp[s[i]];

        while(1){
            string x;
            cin >> x;
            if(x == ":") continue;
            if(x == ";") break;

            if(mp[x] == 0 || mp[x] == node) ok = 0;
            tmp.pb(mp[x]);
        }

        if(!ok){
            cout << "greska\n";
            if(mp[s[i]] == i) mp[s[i]] = 0;

            continue;
        }

        if(tmp.empty()){
            roots[node].pb(node);
            dep[node][node] = 1;
        }

        for(auto j : tmp)
            for(auto k : roots[j])
                v[k].pb(j);

        for(int root = 1; root <= i; ++root) if(v[root].size()){
            cmproot = root;
            sort(all(v[root]), cmp);

            int cur = v[root][0];
            for(auto j : v[root]){
                while(dep[j][root] < dep[cur][root]) cur = p[cur][root];

                if(dep[cur][root] == dep[j][root] && cur != j) ok = 0;
            }
        }

        if(ok){
            cout << "ok\n";

            for(int root = 1; root <= i; ++root) if(v[root].size()){
                p[node][root] = v[root][0];
                dep[node][root] = dep[v[root][0]][root] + 1;
                roots[node].pb(root);

                v[root].clear();
            }

        }
        else{
            cout << "greska\n";

            for(int root = 1; root <= i; ++root) v[root].clear();
            if(mp[s[i]] == i) mp[s[i]] = 0;
        }
    }
    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 4 ms 1108 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 596 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 4 ms 1108 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 800 KB Output is correct
15 Correct 2 ms 568 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 852 KB Output is correct
18 Correct 1 ms 980 KB Output is correct
19 Correct 1 ms 724 KB Output is correct
20 Correct 1 ms 724 KB Output is correct
21 Correct 2 ms 724 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 544 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 7948 KB Output is correct
2 Correct 303 ms 9868 KB Output is correct
3 Correct 215 ms 2352 KB Output is correct
4 Correct 4 ms 2260 KB Output is correct
5 Correct 7 ms 4664 KB Output is correct
6 Correct 13 ms 3532 KB Output is correct
7 Correct 22 ms 3848 KB Output is correct
8 Correct 34 ms 4072 KB Output is correct
9 Correct 32 ms 3736 KB Output is correct
10 Correct 10 ms 3264 KB Output is correct
11 Correct 11 ms 3284 KB Output is correct
12 Correct 237 ms 11216 KB Output is correct