Submission #131551

#	Time	Username	Problem	Language	Result	Execution time	Memory
131551		MrTEK	Meetings (JOI19_meetings)	C++14	29 / 100	160 ms	1956 KiB

meetings

    #include "meetings.h"
    #include <bits/stdc++.h>
    using namespace std;
     
    typedef long long int ll;
    typedef pair <int,int> ii;
     
    const int N = 3e2 + 5;
     
    vector <int> v;
    int mark[N][N],d[N][N];
     
    void bridge(int x,int y) {	
    	Bridge(min(x,y),max(x,y));
    }
     
    void solve(vector <int> v) {
    	if (v.size() < 2)
    		return;
    	if (v.size() == 2) {
    		// cerr << "BEBE BRIDGE " << v[0] << " " << v[1] << endl;
    		bridge(v[0],v[1]);
    		return;
    	}
    	// cerr << "Selam oyun baslasin : " << v[0] << endl;
    	for (int i = 1 ; i < v.size() ; i++) {
    		if (mark[v[0]][i])
    			continue;
    		vector <int> nv;
    		nv.push_back(i);
    		mark[v[0]][i] = 1;
    		for (int j = i + 1 ; j < v.size() ; j++)
    			if (mark[v[0]][j] == 0) {
    				int temp = Query(v[0],v[i],v[j]);
    				if (temp != v[0]) {
    					mark[v[0]][j] = 1;
    					nv.push_back(j);
    					if (temp != v[i])
    						d[v[0]][i] = 1;
    					if (temp != v[j])
    						d[v[0]][j] = 1;
    				}
    			}
    		// cerr << "yeni agac : " << v[0] << " " << v[i] << "\n";
    		vector <int> nv2;
    		for (auto i : nv)
    			nv2.push_back(v[i]);
    		for (int j = 0 ; j < nv.size() ; j++) {
    			if (d[v[0]][nv[j]])
    				continue;
    			bool flag = true;
    			for (int k = j + 1 ; k < nv.size() ; k++) {
    				if (d[v[0]][nv[k]])
    					continue;
    				int temp = Query(v[0],v[nv[j]],v[nv[k]]);
    				if (temp != v[nv[j]]) {
    					flag = false;
    					d[v[0]][nv[j]] = 1;
    					break;
    				}
    				if (temp != v[nv[k]]) {
    					d[v[0]][nv[k]] = 1;
    				}
    			}
    			if (flag == true) {
    				// cerr << "HOLY BRIDGE " << v[0] << " " << v[nv[j]] << endl;				
    				bridge(v[0],v[nv[j]]);
    				break;
    			}
    		}
    		// cerr << nv2.size() << "anaaa " << endl;
    		solve(nv2);
    	}
     
    }
     
    void Solve(int n) {
    	for (int i = 0 ; i < n ; i++)
    		v.push_back(i);
    	solve(v);
    }

Compilation message (stderr)

meetings.cpp: In function 'void solve(std::vector<int>)':
meetings.cpp:28:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int i = 1 ; i < v.size() ; i++) {
                       ~~^~~~~~~~~~
meetings.cpp:34:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = i + 1 ; j < v.size() ; j++)
                            ~~^~~~~~~~~~
meetings.cpp:50:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = 0 ; j < nv.size() ; j++) {
                        ~~^~~~~~~~~~~
meetings.cpp:54:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        for (int k = j + 1 ; k < nv.size() ; k++) {
                             ~~^~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 0 / 71