oj.uz

Submission #362111

# Submission time Handle Problem Language Result Execution time Memory
362111 2021-02-01T19:13:05 Z limabeans Checker (COCI19_checker) C++17
12 / 110
 375 ms 15472 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl




const int maxn = 1e6 + 5;

const string BADTRI = "neispravna triangulacija";
const string NOTPAT = "neispravno bojenje";
const string GOOD = "tocno";


struct iv {
    int l,r,c;
    void read() {
	cin>>l>>r>>c;
	--l; --r;
    }
};

int n;
string s;
vector<iv> w;


int dist(int l, int r) {
    return (r-l+n)%n;

}

string solve() {
    w.clear();
    cin>>n;
    cin>>s;
    w.resize(n-3);
    for (int i=0; i<n-3; i++) {
	w[i].read();
    }
    vector<pair<int,int>> nxt(n);
    for (int i=0; i<n; i++) {
	nxt[i].first = (i+1)%n;
	nxt[i].second = int(s[i]-'0');
    }

    vector<pair<pair<int,int>,int>> diags;
    for (auto p: w) {
	diags.push_back({{p.l,p.r},p.c});
	diags.push_back({{p.r,p.l},p.c});
    }

    sort(diags.begin(), diags.end(), [&](pair<pair<int,int>,int> a, pair<pair<int,int>,int> b) {
	return dist(a.first.first,a.first.second) < dist(b.first.first,b.first.second);
    });



    bool coloring = true;

    for (int i=0; i<n-2; i++) {
	auto cur = diags[i];
	//cout<<cur.first.first+1<<" "<<cur.first.second+1<<endl;
	
	int a = cur.first.first;
	int b = nxt[a].first;
	int c = cur.first.second;
	if (nxt[b].first != c) {
	    return BADTRI;
	}
	vector<int> colors = {cur.second, nxt[a].second, nxt[b].second};
	if ((int)set<int>(colors.begin(), colors.end()).size() < 3) {
	    coloring = false;
	}

	nxt[a] = {c, cur.second};
    }

    if (!coloring) {
	return NOTPAT;
    }


    return GOOD;
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    int t;
    cin>>t;
    while (t--) {
	cout<<solve()<<"\n";
    }
    
    
    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Incorrect 2 ms 492 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 314 ms 15364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 375 ms 15472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Incorrect 2 ms 492 KB Output isn't correct
9 Halted 0 ms 0 KB -