Submission #490206

#	Time	Username	Problem	Language	Result	Execution time	Memory
490206		cpp219	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	240 ms	24012 KiB

supertrees

#include<bits/stdc++.h>
#include "supertrees.h"
#define ll int
#define ld long double
#define fs first
#define sc second
#define debug(y) cout<<y,exit(0)
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 1e3 + 9;
const ll mod = 1e9 + 7;
const ll base = 31;

vector<vector<ll>> ans;
vector<LL> g1,g2;
ll n,ok[N];

int construct(vector<vector<int>> p){
    n = p.size(); ans = p;
    for (ll i = 0;i < n;i++){
        for (ll j = 0;j < n;j++) ans[i][j] = 0;
    }
    for (ll i = 0;i < n;i++)
        for (ll j = 0;j < n;j++) if (p[i][j] == 3) return 0;

    for (ll i = 0;i < n;i++){
        ll now = 0;
        while(p[i][now] != 1) now++;
        if (now != i){
            if (p[i] != p[now]) return 0;
            ans[now][i] = ans[i][now] = 1;
        }
        else ok[i] = 1;
    }

    for(ll i = 0;i < n;i++) if(ok[i]){
		ll cc = 0;
		while(!p[i][cc]) cc++;
		for(ll j = 0;j < n;j++)
			if((p[cc][j] == 0) ^ (p[i][j] == 0)) return 0;
		if(cc == i){
			ll now = i;
			for(ll j = i + 1;j < n;j++)
				if(ok[j] && p[i][j]){
					ans[now][j] = 1; ans[j][now] = 1;
					now = j;
				}

			else if(now != i && ans[now][i]) return 0;
			else if (now != i){
				ans[now][i] = ans[i][now] = 1;
			}
		}
	}
    build(ans);
    return 1;
}
/*
int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "test"
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        //freopen(task".out","w",stdout);
    }
    ll sz; vector<vector<ll>> p;
    cin>>sz;
    for (ll i = 0;i < sz;i++){
        vector<ll> tmp; ll x;
        for (ll j = 0;j < sz;j++) cin>>x,tmp.push_back(x);
        p.push_back(tmp);
    }
    cout<<construct(p)<<"\n";
}
*/
/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 0 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4